Consider an algorithm that takes as input a positive integer n. If n is even, the algorithm divides it by two, and if n is odd, the algorithm multiplies it by three and adds one. The algorithm repeats this, until n is one. For example, the sequence for n=3 is as follows:
3→10→5→16→8→4→2→1
Your task is to simulate the execution of the algorithm for a given value of n.
Input
The only input line contains an integer n.
Output
Print a line that contains all values of n during the algorithm.
Constraints
1≤n≤106
Example
Input: 3
Output: 3 10 5 16 8 4 2 1
Missing Number
CSES - Missing Number
Time limit: 1.00 s
Memory limit: 512 MB
You are given all numbers between 1,2,…,n except one. Your task is to find the missing number.
Input
The first input line contains an integer n.
The second line contains n−1 numbers. Each number is distinct and between 1 and n (inclusive).
Output
Print the missing number.
Constraints
2≤n≤2⋅105
Example
Input: 5
2 3 1 5
Output: 4
Repetitions
CSES - Repetitions
Time limit: 1.00 s
Memory limit: 512 MB
You are given a DNA sequence: a string consisting of characters A, C, G, and T. Your task is to find the longest repetition in the sequence. This is a maximum-length substring containing only one type of character.
Input
The only input line contains a string of n characters.
Output
Print one integer: the length of the longest repetition.
Constraints
1≤n≤106
Example
Input: ATTCGGGA
Output: 3
Increasing Array
CSES - Increasing Array
Time limit: 1.00 s
Memory limit: 512 MB
You are given an array of n integers. You want to modify the array so that it is increasing, i.e., every element is at least as large as the previous element.
On each move, you may increase the value of any element by one. What is the minimum number of moves required?
Input
The first input line contains an integer n: the size of the array.
Then, the second line contains n integers x1,x2,…,xn: the contents of the array.
Output
Print the minimum number of moves.
Constraints
1≤n≤2⋅105
1≤xi≤109
Example
Input: 5
3 2 5 1 7
Output: 5
Permutations
CSES - Permutations
Time limit: 1.00 s
Memory limit: 512 MB
A permutation of integers 1,2,…,n is called beautiful if there are no adjacent elements whose difference is 1.
Given n, construct a beautiful permutation if such a permutation exists.
Input
The only input line contains an integer n.
Output
Print a beautiful permutation of integers 1,2,…,n. If there are several solutions, you may print any of them. If there are no solutions, print "NO SOLUTION".
Constraints
1≤n≤106
Example 1
Input: 5
Output: 4 2 5 3 1
Example 2
Input: 3
Output: NO SOLUTION
Number Spiral
CSES - Number Spiral
Time limit: 1.00 s
Memory limit: 512 MB
A number spiral is an infinite grid whose upper-left square has number 1. Here are the first five layers of the spiral:
Your task is to find out the number in row y and column x.
Input
The first input line contains an integer t: the number of tests.
After this, there are t lines, each containing integers y and x.
Output
For each test, print the number in row y and column x.
Constraints
1≤t≤105
1≤y,x≤109
Example
Input: 3
2 3
1 1
4 2
Output: 8
1
15
CSES - Two Knights
Time limit: 1.00 s
Memory limit: 512 MB
Your task is to count for k=1,2,…,n the number of ways two knights can be placed on a k×k chessboard so that they do not attack each other.
Input
The only input line contains an integer n.
Output
Print n integers: the results.
Constraints
1≤n≤10000
Example
Input: 8
Output: 0
6
28
96
252
550
1056
1848
CSES - Two Sets
Time limit: 1.00 s
Memory limit: 512 MB
Your task is to divide the numbers 1,2,…,n into two sets of equal sum.
Input
The only input line contains an integer n.
Output
Print "YES", if the division is possible, and "NO" otherwise.
After this, if the division is possible, print an example of how to create the sets. First, print the number of elements in the first set followed by the elements themselves in a separate line, and then, print the second set in a similar way.
Constraints
1≤n≤106
Example 1
Input: 7
Output: YES
4
1 2 4 7
3
3 5 6
Example 2
Input: 6
Output: NO
Bit Strings
CSES - Bit Strings
Time limit: 1.00 s
Memory limit: 512 MB
Your task is to calculate the number of bit strings of length n.
For example, if n=3, the correct answer is 8, because the possible bit strings are 000, 001, 010, 011, 100, 101, 110, and 111.
Input
The only input line has an integer n.
Output
Print the result modulo 109+7.
Constraints
1≤n≤106
Example
Input: 3
Output: 8
Trailing Zeroes
CSES - Trailing Zeros
Time limit: 1.00 s
Memory limit: 512 MB
Your task is to calculate the number of trailing zeros in the factorial n!.
For example, 20!=2432902008176640000 and it has 4 trailing zeros.
Input
The only input line has an integer n.
Output
Print the number of trailing zeros in n!.
Constraints
1≤n≤109
Example
Input: 20
Output: 4
Coin Piles
CSES - Coin Piles
Time limit: 1.00 s
Memory limit: 512 MB
You have two coin piles containing a and b coins. On each move, you can either remove one coin from the left pile and two coins from the right pile, or two coins from the left pile and one coin from the right pile.
Your task is to efficiently find out if you can empty both the piles.
Input
The first input line has an integer t: the number of tests.
After this, there are t lines, each of which has two integers a and b: the numbers of coins in the piles.
Output
For each test, print "YES" if you can empty the piles and "NO" otherwise.
Constraints
1≤t≤105
0≤a,b≤109
Example
Input: 3
2 1
2 2
3 3
Output: YES
NO
YES
Palinderome Reorder
CSES - Palindrome Reorder
Time limit: 1.00 s
Memory limit: 512 MB
Given a string, your task is to reorder its letters in such a way that it becomes a palindrome (i.e., it reads the same forwards and backwards).
Input
The only input line has a string of length n consisting of characters A–Z.
Output
Print a palindrome consisting of the characters of the original string. You may print any valid solution. If there are no solutions, print "NO SOLUTION".
Constraints
1≤n≤106
Example
Input: AAAACACBA
Output: AACABACAA
Gray Code
CSES - Gray Code
Time limit: 1.00 s
Memory limit: 512 MB
A Gray code is a list of all 2n bit strings of length n, where any two successive strings differ in exactly one bit (i.e., their Hamming distance is one).
Your task is to create a Gray code for a given length n.
Input
The only input line has an integer n.
Output
Print 2n lines that describe the Gray code. You can print any valid solution.
Constraints
1≤n≤16
Example
Input: 2
Output: 00
01
11
10
Tower of Hanoi
CSES - Gray Code
Time limit: 1.00 s
Memory limit: 512 MB
A Gray code is a list of all 2n bit strings of length n, where any two successive strings differ in exactly one bit (i.e., their Hamming distance is one).
Your task is to create a Gray code for a given length n.
Input
The only input line has an integer n.
Output
Print 2n lines that describe the Gray code. You can print any valid solution.
Constraints
1≤n≤16
Example
Input: 2
Output: 00
01
11
10
Tower of Hanoi
CSES - Tower of Hanoi
Time limit: 1.00 s
Memory limit: 512 MB
The Tower of Hanoi game consists of three stacks (left, middle and right) and n round disks of different sizes. Initially, the left stack has all the disks, in increasing order of size from top to bottom.
The goal is to move all the disks to the right stack using the middle stack. On each move you can move the uppermost disk from a stack to another stack. In addition, it is not allowed to place a larger disk on a smaller disk.
Your task is to find a solution that minimizes the number of moves.
Input
The only input line has an integer n: the number of disks.
Output
First print an integer k: the minimum number of moves.
After this, print k lines that describe the moves. Each line has two integers a and b: you move a disk from stack a to stack b.
Constraints
1≤n≤16
Example
Input: 2
Output: 3
1 2
1 3
2 3
Creating Strings
CSES - Creating Strings
Time limit: 1.00 s
Memory limit: 512 MB
Given a string, your task is to generate all different strings that can be created using its characters.
Input
The only input line has a string of length n. Each character is between a–z.
Output
First print an integer k: the number of strings. Then print k lines: the strings in alphabetical order.
There are n apples with known weights. Your task is to divide the apples into two groups so that the difference between the weights of the groups is minimal.
Input
The first input line has an integer n: the number of apples.
The next line has n integers p1,p2,…,pn: the weight of each apple.
Output
Print one integer: the minimum difference between the weights of the groups.
Constraints
1≤n≤20
1≤pi≤109
Example
Input: 5
3 2 7 4 1
Output: 1
Explanation: Group 1 has weights 2, 3 and 4 (total weight 9), and group 2 has weights 1 and 7 (total weight 8).
Chessboard and Queens
CSES - Chessboard and Queens
Time limit: 1.00 s
Memory limit: 512 MB
Your task is to place eight queens on a chessboard so that no two queens are attacking each other. As an additional challenge, each square is either free or reserved, and you can only place queens on the free squares. However, the reserved squares do not prevent queens from attacking each other.
How many possible ways are there to place the queens?
Input
The input has eight lines, and each of them has eight characters. Each square is either free (.) or reserved (*).
Output
Print one integer: the number of ways you can place the queens.
Consider an infinite string that consists of all positive integers in increasing order:
12345678910111213141516171819202122232425...
Your task is to process q queries of the form: what is the digit at position k in the string?
Input
The first input line has an integer q: the number of queries.
After this, there are q lines that describe the queries. Each line has an integer k: a 1-indexed position in the string.
Output
For each query, print the corresponding digit.
Constraints
1≤q≤1000
1≤k≤1018
Example
Input: 3
7
19
12
Output: 7
4
1
Grid Paths
CSES - Grid Paths
Time limit: 1.00 s
Memory limit: 512 MB
There are 88418 paths in a 7×7 grid from the upper-left square to the lower-left square. Each path corresponds to a 48-character description consisting of characters D (down), U (up), L (left) and R (right).
For example, the path
corresponds to the description DRURRRRRDDDLUULDDDLDRRURDDLLLLLURULURRUULDLLDDDD.
You are given a description of a path which may also contain characters ? (any direction). Your task is to calculate the number of paths that match the description.
Input
The only input line has a 48-character string of characters ?, D, U, L and R.
You are given a list of n integers, and your task is to calculate the number of distinct values in the list.
Input
The first input line has an integer n: the number of values.
The second line has n integers x1,x2,…,xn.
Output
Print one integers: the number of distinct values.
Constraints
1≤n≤2⋅105
1≤xi≤109
Example
Input: 5
2 3 2 2 3
Output: 2
Apartments
CSES - Apartments
Time limit: 1.00 s
Memory limit: 512 MB
There are n applicants and m free apartments. Your task is to distribute the apartments so that as many applicants as possible will get an apartment.
Each applicant has a desired apartment size, and they will accept any apartment whose size is close enough to the desired size.
Input
The first input line has three integers n, m, and k: the number of applicants, the number of apartments, and the maximum allowed difference.
The next line contains n integers a1,a2,…,an: the desired apartment size of each applicant. If the desired size of an applicant is x, he or she will accept any apartment whose size is between x−k and x+k.
The last line contains m integers b1,b2,…,bm: the size of each apartment.
Output
Print one integer: the number of applicants who will get an apartment.
Constraints
1≤n,m≤2⋅105
0≤k≤109
1≤ai,bi≤109
Example
Input: 4 3 5
60 45 80 60
30 60 75
Output: 2
Ferris Wheel
CSES - Ferris Wheel
Time limit: 1.00 s
Memory limit: 512 MB
There are n children who want to go to a Ferris wheel, and your task is to find a gondola for each child.
Each gondola may have one or two children in it, and in addition, the total weight in a gondola may not exceed x. You know the weight of every child.
What is the minimum number of gondolas needed for the children?
Input
The first input line contains two integers n and x: the number of children and the maximum allowed weight.
The next line contains n integers p1,p2,…,pn: the weight of each child.
Output
Print one integer: the minimum number of gondolas.
Constraints
1≤n≤2⋅105
1≤x≤109
1≤pi≤x
Example
Input: 4 10
7 2 3 9
Output: 3
Concert Tickets
CSES - Concert Tickets
Time limit: 1.00 s
Memory limit: 512 MB
There are n concert tickets available, each with a certain price. Then, m customers arrive, one after another.
Each customer announces the maximum price they are willing to pay for a ticket, and after this, they will get a ticket with the nearest possible price such that it does not exceed the maximum price.
Input
The first input line contains integers n and m: the number of tickets and the number of customers.
The next line contains n integers h1,h2,…,hn: the price of each ticket.
The last line contains m integers t1,t2,…,tm: the maximum price for each customer in the order they arrive.
Output
Print, for each customer, the price that they will pay for their ticket. After this, the ticket cannot be purchased again.
If a customer cannot get any ticket, print −1.
Constraints
1≤n,m≤2⋅105
1≤hi,ti≤109
Example
Input: 5 3
5 3 7 8 5
4 8 3
Output: 3
8
-1
Restaurant Customers
CSES - Restaurant Customers
Time limit: 1.00 s
Memory limit: 512 MB
You are given the arrival and leaving times of n customers in a restaurant.
What was the maximum number of customers in the restaurant at any time?
Input
The first input line has an integer n: the number of customers.
After this, there are n lines that describe the customers. Each line has two integers a and b: the arrival and leaving times of a customer.
You may assume that all arrival and leaving times are distinct.
Output
Print one integer: the maximum number of customers.
Constraints
1≤n≤2⋅105
1≤a<b≤109
Example
Input: 3
5 8
2 4
3 9
Output: 2
Movie Festival
CSES - Movie Festival
Time limit: 1.00 s
Memory limit: 512 MB
In a movie festival n movies will be shown. You know the starting and ending time of each movie. What is the maximum number of movies you can watch entirely?
Input
The first input line has an integer n: the number of movies.
After this, there are n lines that describe the movies. Each line has two integers a and b: the starting and ending times of a movie.
Output
Print one integer: the maximum number of movies.
Constraints
1≤n≤2⋅105
1≤a<b≤109
Example
Input: 3
3 5
4 9
5 8
Output: 2
Sum of Two Values
CSES - Sum of Two Values
Time limit: 1.00 s
Memory limit: 512 MB
You are given an array of n integers, and your task is to find two values (at distinct positions) whose sum is x.
Input
The first input line has two integers n and x: the array size and the target sum.
The second line has n integers a1,a2,…,an: the array values.
Output
Print two integers: the positions of the values. If there are several solutions, you may print any of them. If there are no solutions, print IMPOSSIBLE.
Constraints
1≤n≤2⋅105
1≤x,ai≤109
Example
Input: 4 8
2 7 5 1
Output: 2 4
Maximum Subarray Sum
CSES - Maximum Subarray Sum
Time limit: 1.00 s
Memory limit: 512 MB
Given an array of n integers, your task is to find the maximum sum of values in a contiguous, nonempty subarray.
Input
The first input line has an integer n: the size of the array.
The second line has n integers x1,x2,…,xn: the array values.
Output
Print one integer: the maximum subarray sum.
Constraints
1≤n≤2⋅105
−109≤xi≤109
Example
Input: 8
-1 3 -2 5 3 -5 2 2
Output: 9
Stick Lengths
CSES - Stick Lengths
Time limit: 1.00 s
Memory limit: 512 MB
There are n sticks with some lengths. Your task is to modify the sticks so that each stick has the same length.
You can either lengthen and shorten each stick. Both operations cost x where x is the difference between the new and original length.
What is the minimum total cost?
Input
The first input line contains an integer n: the number of sticks.
Then there are n integers: p1,p2,…,pn: the lengths of the sticks.
Output
Print one integer: the minimum total cost.
Constraints
1≤n≤2⋅105
1≤pi≤109
Example
Input: 5
2 3 1 5 2
Output: 5
Missing Coin Sum
CSES - Missing Coin Sum
Time limit: 1.00 s
Memory limit: 512 MB
You have n coins with positive integer values. What is the smallest sum you cannot create using a subset of the coins?
Input
The first input line has an integer n: the number of coins.
The second line has n integers x1,x2,…,xn: the value of each coin.
Output
Print one integer: the smallest coin sum.
Constraints
1≤n≤2⋅105
1≤xi≤109
Example
Input: 5
2 9 1 2 7
Output: 6
Collecting NUmbers
CSES - Collecting Numbers
Time limit: 1.00 s
Memory limit: 512 MB
You are given an array that contains each number between 1…n exactly once. Your task is to collect the numbers from 1 to n in increasing order.
On each round, you go through the array from left to right and collect as many numbers as possible. What will be the total number of rounds?
Input
The first line has an integer n: the array size.
The next line has n integers x1,x2,…,xn: the numbers in the array.
Output
Print one integer: the number of rounds.
Constraints
1≤n≤2⋅105
Example
Input: 5
4 2 1 5 3
Output: 3
Collecting Numbers II
CSES - Collecting Numbers II
Time limit: 1.00 s
Memory limit: 512 MB
You are given an array that contains each number between 1…n exactly once. Your task is to collect the numbers from 1 to n in increasing order.
On each round, you go through the array from left to right and collect as many numbers as possible.
Given m operations that swap two numbers in the array, your task is to report the number of rounds after each operation.
Input
The first line has two integers n and m: the array size and the number of operations.
The next line has n integers x1,x2,…,xn: the numbers in the array.
Finally, there are m lines that describe the operations. Each line has two integers a and b: the numbers at positions a and b are swapped.
Output
Print m integers: the number of rounds after each swap.
Constraints
1≤n,m≤2⋅105
1≤a,b≤n
Example
Input: 5 3
4 2 1 5 3
2 3
1 5
2 3
Output: 2
3
4
PLaylist
CSES - Playlist
Time limit: 1.00 s
Memory limit: 512 MB
You are given a playlist of a radio station since its establishment. The playlist has a total of n songs.
What is the longest sequence of successive songs where each song is unique?
Input
The first input line contains an integer n: the number of songs.
The next line has n integers k1,k2,…,kn: the id number of each song.
Output
Print the length of the longest sequence of unique songs.
Constraints
1≤n≤2⋅105
1≤ki≤109
Example
Input: 8
1 2 1 3 2 7 4 2
Output: 5
Towers
CSES - Towers
Time limit: 1.00 s
Memory limit: 512 MB
You are given n cubes in a certain order, and your task is to build towers using them. Whenever two cubes are one on top of the other, the upper cube must be smaller than the lower cube.
You must process the cubes in the given order. You can always either place the cube on top of an existing tower, or begin a new tower. What is the minimum possible number of towers?
Input
The first input line contains an integer n: the number of cubes.
The next line contains n integers k1,k2,…,kn: the sizes of the cubes.
Output
Print one integer: the minimum number of towers.
Constraints
1≤n≤2⋅105
1≤ki≤109
Example
Input: 5
3 8 2 1 5
Output: 2
Traffic Lights
CSES - Traffic Lights
Time limit: 1.00 s
Memory limit: 512 MB
There is a street of length x whose positions are numbered 0,1,…,x. Initially there are no traffic lights, but n sets of traffic lights are added to the street one after another.
Your task is to calculate the length of the longest passage without traffic lights after each addition.
Input
The first input line contains two integers x and n: the length of the street and the number of sets of traffic lights.
Then, the next line contains n integers p1,p2,…,pn: the position of each set of traffic lights. Each position is distinct.
Output
Print the length of the longest passage without traffic lights after each addition.
Constraints
1≤x≤109
1≤n≤2⋅105
0<pi<x
Example
Input: 8 3
3 6 2
Output: 5 3 3
Joshephus Problem I
CSES - Josephus Problem I
Time limit: 1.00 s
Memory limit: 512 MB
Consider a game where there are n children (numbered 1,2,…,n) in a circle. During the game, every second child is removed from the circle, until there are no children left. In which order will the children be removed?
Input
The only input line has an integer n.
Output
Print n integers: the removal order.
Constraints
1≤n≤2⋅105
Example
Input: 7
Output: 2 4 6 1 5 3 7
Joshephus Problem II
CSES - Josephus Problem II
Time limit: 1.00 s
Memory limit: 512 MB
Consider a game where there are n children (numbered 1,2,…,n) in a circle. During the game, repeatedly k children are skipped and one child is removed from the circle. In which order will the children be removed?
Input
The only input line has two integers n and k.
Output
Print n integers: the removal order.
Constraints
1≤n≤2⋅105
0≤k≤109
Example
Input: 7 2
Output: 3 6 2 7 5 1 4
Nested Ranges Check
CSES - Nested Ranges Check
Time limit: 1.00 s
Memory limit: 512 MB
Given n ranges, your task is to determine for each range if it contains some other range and if some other range contains it.
Range [a,b] contains range [c,d] if a≤c and d≤b.
Input
The first input line has an integer n: the number of ranges.
After this, there are n lines that describe the ranges. Each line has two integers x and y: the range is [x,y].
You may assume that no range appears more than once in the input.
Output
First print a line that describes for each range (in the input order) if it contains some other range (1) or not (0).
Then print a line that describes for each range (in the input order) if some other range contains it (1) or not (0).
Constraints
1≤n≤2⋅105
1≤x<y≤109
Example
Input: 4
1 6
2 4
4 8
3 6
Output: 1 0 0 0
0 1 0 1
Nested Ranges Count
CSES - Nested Ranges Count
Time limit: 1.00 s
Memory limit: 512 MB
Given n ranges, your task is to count for each range how many other ranges it contains and how many other ranges contain it.
Range [a,b] contains range [c,d] if a≤c and d≤b.
Input
The first input line has an integer n: the number of ranges.
After this, there are n lines that describe the ranges. Each line has two integers x and y: the range is [x,y].
You may assume that no range appears more than once in the input.
Output
First print a line that describes for each range (in the input order) how many other ranges it contains.
Then print a line that describes for each range (in the input order) how many other ranges contain it.
Constraints
1≤n≤2⋅105
1≤x<y≤109
Example
Input: 4
1 6
2 4
4 8
3 6
Output: 2 0 0 0
0 1 0 1
Room Allocation
CSES - Room Allocation
Time limit: 1.00 s
Memory limit: 512 MB
There is a large hotel, and n customers will arrive soon. Each customer wants to have a single room.
You know each customer's arrival and departure day. Two customers can stay in the same room if the departure day of the first customer is earlier than the arrival day of the second customer.
What is the minimum number of rooms that are needed to accommodate all customers? And how can the rooms be allocated?
Input
The first input line contains an integer n: the number of customers.
Then there are n lines, each of which describes one customer. Each line has two integers a and b: the arrival and departure day.
Output
Print first an integer k: the minimum number of rooms required.
After that, print a line that contains the room number of each customer in the same order as in the input. The rooms are numbered 1,2,…,k. You can print any valid solution.
Constraints
1≤n≤2⋅105
1≤a≤b≤109
Example
Input: 3
1 2
2 4
4 4
Output: 2
1 2 1
Factory Machines
CSES - Factory Machines
Time limit: 1.00 s
Memory limit: 512 MB
A factory has n machines which can be used to make products. Your goal is to make a total of t products.
For each machine, you know the number of seconds it needs to make a single product. The machines can work simultaneously, and you can freely decide their schedule.
What is the shortest time needed to make t products?
Input
The first input line has two integers n and t: the number of machines and products.
The next line has n integers k1,k2,…,kn: the time needed to make a product using each machine.
Output
Print one integer: the minimum time needed to make t products.
Constraints
1≤n≤2⋅105
1≤t≤109
1≤ki≤109
Example
Input: 3 7
3 2 5
Output: 8
Explanation: Machine 1 makes two products, machine 2 makes four products and machine 3 makes one product.
Task and Deadlines
CSES - Tasks and Deadlines
Time limit: 1.00 s
Memory limit: 512 MB
You have to process n tasks. Each task has a duration and a deadline, and you will process the tasks in some order one after another. Your reward for a task is d−f where d is its deadline and f is your finishing time. (The starting time is 0, and you have to process all tasks even if a task would yield negative reward.)
What is your maximum reward if you act optimally?
Input
The first input line has an integer n: the number of tasks.
After this, there are n lines that describe the tasks. Each line has two integers a and d: the duration and deadline of the task.
Output
Print one integer: the maximum reward.
Constraints
1≤n≤2⋅105
1≤a,d≤106
Example
Input: 3
6 10
8 15
5 12
Output: 2
Reading Books
CSES - Reading Books
Time limit: 1.00 s
Memory limit: 512 MB
There are n books, and Kotivalo and Justiina are going to read them all. For each book, you know the time it takes to read it.
They both read each book from beginning to end, and they cannot read a book at the same time. What is the minimum total time required?
Input
The first input line has an integer n: the number of books.
The second line has n integers t1,t2,…,tn: the time required to read each book.
Output
Print one integer: the minimum total time.
Constraints
1≤n≤2⋅105
1≤ti≤109
Example
Input: 3
2 8 3
Output: 16
Sum Of Three Values
CSES - Sum of Three Values
Time limit: 1.00 s
Memory limit: 512 MB
You are given an array of n integers, and your task is to find three values (at distinct positions) whose sum is x.
Input
The first input line has two integers n and x: the array size and the target sum.
The second line has n integers a1,a2,…,an: the array values.
Output
Print three integers: the positions of the values. If there are several solutions, you may print any of them. If there are no solutions, print IMPOSSIBLE.
Constraints
1≤n≤5000
1≤x,ai≤109
Example
Input: 4 8
2 7 5 1
Output: 1 3 4
Sum of Four Values
CSES - Sum of Four Values
Time limit: 1.00 s
Memory limit: 512 MB
You are given an array of n integers, and your task is to find four values (at distinct positions) whose sum is x.
Input
The first input line has two integers n and x: the array size and the target sum.
The second line has n integers a1,a2,…,an: the array values.
Output
Print four integers: the positions of the values. If there are several solutions, you may print any of them. If there are no solutions, print IMPOSSIBLE.
Constraints
1≤n≤1000
1≤x,ai≤109
Example
Input: 8 15
3 2 5 8 1 3 2 3
Output: 2 4 6 7
Nearest Smaller Values
CSES - Nearest Smaller Values
Time limit: 1.00 s
Memory limit: 512 MB
Given an array of n integers, your task is to find for each array position the nearest position to its left having a smaller value.
Input
The first input line has an integer n: the size of the array.
The second line has n integers x1,x2,…,xn: the array values.
Output
Print n integers: for each array position the nearest position with a smaller value. If there is no such position, print 0.
Constraints
1≤n≤2⋅105
1≤xi≤109
Example
Input: 8
2 5 1 4 8 3 2 5
Output: 0 1 0 3 4 3 3 7
Subarray Sums I
CSES - Subarray Sums I
Time limit: 1.00 s
Memory limit: 512 MB
Given an array of n positive integers, your task is to count the number of subarrays having sum x.
Input
The first input line has two integers n and x: the size of the array and the target sum x.
The next line has n integers a1,a2,…,an: the contents of the array.
Output
Print one integer: the required number of subarrays.
Constraints
1≤n≤2⋅105
1≤x,ai≤109
Example
Input: 5 7
2 4 1 2 7
Output: 3
Subarray Sums II
CSES - Subarray Sums II
Time limit: 1.00 s
Memory limit: 512 MB
Given an array of n integers, your task is to count the number of subarrays having sum x.
Input
The first input line has two integers n and x: the size of the array and the target sum x.
The next line has n integers a1,a2,…,an: the contents of the array.
Output
Print one integer: the required number of subarrays.
Constraints
1≤n≤2⋅105
−109≤x,ai≤109
Example
Input: 5 7
2 -1 3 5 -2
Output: 2
Subarray Divisibility
CSES - Subarray Divisibility
Time limit: 1.00 s
Memory limit: 512 MB
Given an array of n integers, your task is to count the number of subarrays where the sum of values is divisible by n.
Input
The first input line has an integer n: the size of the array.
The next line has n integers a1,a2,…,an: the contents of the array.
Output
Print one integer: the required number of subarrays.
Constraints
1≤n≤2⋅105
−109≤ai≤109
Example
Input: 5
3 1 2 7 4
Output: 1
Subarray Distinct Values
CSES - Subarray Distinct Values
Time limit: 1.00 s
Memory limit: 512 MB
Given an array of n integers, your task is to calculate the number of subarrays that have at most k distinct values.
Input
The first input line has two integers n and k.
The next line has n integers x1,x2,…,xn: the contents of the array.
Output
Print one integer: the number of subarrays.
Constraints
1≤k≤n≤2⋅105
1≤xi≤109
Example
Input: 5 2
1 2 3 1 1
Output: 10
Array Division
CSES - Array Division
Time limit: 1.00 s
Memory limit: 512 MB
You are given an array containing n positive integers.
Your task is to divide the array into k subarrays so that the maximum sum in a subarray is as small as possible.
Input
The first input line contains two integers n and k: the size of the array and the number of subarrays in the division.
The next line contains n integers x1,x2,…,xn: the contents of the array.
Output
Print one integer: the maximum sum in a subarray in the optimal division.
Constraints
1≤n≤2⋅105
1≤k≤n
1≤xi≤109
Example
Input: 5 3
2 4 7 3 5
Output: 8
Explanation: An optimal division is [2,4],[7],[3,5] where the sums of the subarrays are 6,7,8. The largest sum is the last sum 8.
Sliding Median
CSES - Sliding Median
Time limit: 1.00 s
Memory limit: 512 MB
You are given an array of n integers. Your task is to calculate the median of each window of k elements, from left to right.
The median is the middle element when the elements are sorted. If the number of elements is even, there are two possible medians and we assume that the median is the smaller of them.
Input
The first input line contains two integers n and k: the number of elements and the size of the window.
Then there are n integers x1,x2,…,xn: the contents of the array.
Output
Print n−k+1 values: the medians.
Constraints
1≤k≤n≤2⋅105
1≤xi≤109
Example
Input: 8 3
2 4 3 5 8 1 2 1
Output: 3 4 5 5 2 1
Sliding Cost
CSES - Sliding Cost
Time limit: 1.00 s
Memory limit: 512 MB
You are given an array of n integers. Your task is to calculate for each window of k elements, from left to right, the minimum total cost of making all elements equal.
You can increase or decrease each element with cost x where x is the difference between the new and the original value. The total cost is the sum of such costs.
Input
The first input line contains two integers n and k: the number of elements and the size of the window.
Then there are n integers x1,x2,…,xn: the contents of the array.
Output
Output n−k+1 values: the costs.
Constraints
1≤k≤n≤2⋅105
1≤xi≤109
Example
Input: 8 3
2 4 3 5 8 1 2 1
Output: 2 2 5 7 7 1
Movie Festival II
CSES - Movie Festival II
Time limit: 1.00 s
Memory limit: 512 MB
In a movie festival, n movies will be shown. Syrjälä's movie club consists of k members, who will be all attending the festival.
You know the starting and ending time of each movie. What is the maximum total number of movies the club members can watch entirely if they act optimally?
Input
The first input line has two integers n and k: the number of movies and club members.
After this, there are n lines that describe the movies. Each line has two integers a and b: the starting and ending time of a movie.
Output
Print one integer: the maximum total number of movies.
Constraints
1≤k≤n≤2⋅105
1≤a<b≤109
Example
Input: 5 2
1 5
8 10
3 6
2 5
6 9
Output: 4
Maximum Subarraysum II
CSES - Maximum Subarray Sum II
Time limit: 1.00 s
Memory limit: 512 MB
Given an array of n integers, your task is to find the maximum sum of values in a contiguous subarray with length between a and b.
Input
The first input line has three integers n, a and b: the size of the array and the minimum and maximum subarray length.
The second line has n integers x1,x2,…,xn: the array values.
Output
Print one integer: the maximum subarray sum.
Constraints
1≤n≤2⋅105
1≤a≤b≤n
−109≤xi≤109
Example
Input: 8 1 2
-1 3 -2 5 3 -5 2 2
Output: 8
Dynamic Programming
Dice Combinations
CSES - Dice Combinations
Time limit: 1.00 s
Memory limit: 512 MB
Your task is to count the number of ways to construct sum n by throwing a dice one or more times. Each throw produces an outcome between 1 and 6.
For example, if n=3, there are 4 ways:
1+1+1
1+2
2+1
3
Input
The only input line has an integer n.
Output
Print the number of ways modulo 109+7.
Constraints
1≤n≤106
Example
Input: 3
Output: 4
Minimizing Coins
CSES - Minimizing Coins
Time limit: 1.00 s
Memory limit: 512 MB
Consider a money system consisting of n coins. Each coin has a positive integer value. Your task is to produce a sum of money x using the available coins in such a way that the number of coins is minimal.
For example, if the coins are {1,5,7} and the desired sum is 11, an optimal solution is 5+5+1 which requires 3 coins.
Input
The first input line has two integers n and x: the number of coins and the desired sum of money.
The second line has n distinct integers c1,c2,…,cn: the value of each coin.
Output
Print one integer: the minimum number of coins. If it is not possible to produce the desired sum, print −1.
Constraints
1≤n≤100
1≤x≤106
1≤ci≤106
Example
Input: 3 11
1 5 7
Output: 3
Coin Combinations I
CSES - Coin Combinations I
Time limit: 1.00 s
Memory limit: 512 MB
Consider a money system consisting of n coins. Each coin has a positive integer value. Your task is to calculate the number of distinct ways you can produce a money sum x using the available coins.
For example, if the coins are {2,3,5} and the desired sum is 9, there are 8 ways:
2+2+5
2+5+2
5+2+2
3+3+3
2+2+2+3
2+2+3+2
2+3+2+2
3+2+2+2
Input
The first input line has two integers n and x: the number of coins and the desired sum of money.
The second line has n distinct integers c1,c2,…,cn: the value of each coin.
Output
Print one integer: the number of ways modulo 109+7.
Constraints
1≤n≤100
1≤x≤106
1≤ci≤106
Example
Input: 3 9
2 3 5
Output: 8
Coin COmbinations II
CSES - Coin Combinations II
Time limit: 1.00 s
Memory limit: 512 MB
Consider a money system consisting of n coins. Each coin has a positive integer value. Your task is to calculate the number of distinct ordered ways you can produce a money sum x using the available coins.
For example, if the coins are {2,3,5} and the desired sum is 9, there are 3 ways:
2+2+5
3+3+3
2+2+2+3
Input
The first input line has two integers n and x: the number of coins and the desired sum of money.
The second line has n distinct integers c1,c2,…,cn: the value of each coin.
Output
Print one integer: the number of ways modulo 109+7.
Constraints
1≤n≤100
1≤x≤106
1≤ci≤106
Example
Input: 3 9
2 3 5
Output: 3
Removing Digits
CSES - Removing Digits
Time limit: 1.00 s
Memory limit: 512 MB
You are given an integer n. On each step, you may subtract one of the digits from the number.
How many steps are required to make the number equal to 0?
Input
The only input line has an integer n.
Output
Print one integer: the minimum number of steps.
Constraints
1≤n≤106
Example
Input: 27
Output: 5
Explanation: An optimal solution is 27→20→18→10→9→0.
Grid Paths
CSES - Grid Paths
Time limit: 1.00 s
Memory limit: 512 MB
Consider an n×n grid whose squares may have traps. It is not allowed to move to a square with a trap.
Your task is to calculate the number of paths from the upper-left square to the lower-right square. You can only move right or down.
Input
The first input line has an integer n: the size of the grid.
After this, there are n lines that describe the grid. Each line has n characters: . denotes an empty cell, and * denotes a trap.
Output
Print the number of paths modulo 109+7.
Constraints
1≤n≤1000
Example
Input: 4
....
.*..
...*
*...
Output: 3
Book Shop
CSES - Book Shop
Time limit: 1.00 s
Memory limit: 512 MB
You are in a book shop which sells n different books. You know the price and number of pages of each book.
You have decided that the total price of your purchases will be at most x. What is the maximum number of pages you can buy? You can buy each book at most once.
Input
The first input line contains two integers n and x: the number of books and the maximum total price.
The next line contains n integers h1,h2,…,hn: the price of each book.
The last line contains n integers s1,s2,…,sn: the number of pages of each book.
Output
Print one integer: the maximum number of pages.
Constraints
1≤n≤1000
1≤x≤105
1≤hi,si≤1000
Example
Input: 4 10
4 8 5 3
5 12 8 1
Output: 13
Explanation: You can buy books 1 and 3. Their price is 4+5=9 and the number of pages is 5+8=13.
Array Description
CSES - Array Description
Time limit: 1.00 s
Memory limit: 512 MB
You know that an array has n integers between 1 and m, and the absolute difference between two adjacent values is at most 1.
Given a description of the array where some values may be unknown, your task is to count the number of arrays that match the description.
Input
The first input line has two integers n and m: the array size and the upper bound for each value.
The next line has n integers x1,x2,…,xn: the contents of the array. Value 0 denotes an unknown value.
Output
Print one integer: the number of arrays modulo 109+7.
Constraints
1≤n≤105
1≤m≤100
0≤xi≤m
Example
Input: 3 5
2 0 2
Output: 3
Explanation: The arrays [2,1,2], [2,2,2] and [2,3,2] match the description.
Counting Towers
CSES - Array Description
Time limit: 1.00 s
Memory limit: 512 MB
You know that an array has n integers between 1 and m, and the absolute difference between two adjacent values is at most 1.
Given a description of the array where some values may be unknown, your task is to count the number of arrays that match the description.
Input
The first input line has two integers n and m: the array size and the upper bound for each value.
The next line has n integers x1,x2,…,xn: the contents of the array. Value 0 denotes an unknown value.
Output
Print one integer: the number of arrays modulo 109+7.
Constraints
1≤n≤105
1≤m≤100
0≤xi≤m
Example
Input: 3 5
2 0 2
Output: 3
Explanation: The arrays [2,1,2], [2,2,2] and [2,3,2] match the description.
Edit Distance
CSES - Edit Distance
Time limit: 1.00 s
Memory limit: 512 MB
The edit distance between two strings is the minimum number of operations required to transform one string into the other.
The allowed operations are:
Add one character to the string.
Remove one character from the string.
Replace one character in the string.
For example, the edit distance between LOVE and MOVIE is 2, because you can first replace L with M, and then add I.
Your task is to calculate the edit distance between two strings.
Input
The first input line has a string that contains n characters between A–Z.
The second input line has a string that contains m characters between A–Z.
Output
Print one integer: the edit distance between the strings.
Constraints
1≤n,m≤5000
Example
Input: LOVE
MOVIE
Output: 2
Rectangle Cutting
CSES - Rectangle Cutting
Time limit: 1.00 s
Memory limit: 512 MB
Given an a×b rectangle, your task is to cut it into squares. On each move you can select a rectangle and cut it into two rectangles in such a way that all side lengths remain integers. What is the minimum possible number of moves?
Input
The only input line has two integers a and b.
Output
Print one integer: the minimum number of moves.
Constraints
1≤a,b≤500
Example
Input: 3 5
Output: 3
Money Sums
CSES - Money Sums
Time limit: 1.00 s
Memory limit: 512 MB
You have n coins with certain values. Your task is to find all money sums you can create using these coins.
Input
The first input line has an integer n: the number of coins.
The next line has n integers x1,x2,…,xn: the values of the coins.
Output
First print an integer k: the number of distinct money sums. After this, print all possible sums in increasing order.
Constraints
1≤n≤100
1≤xi≤1000
Example
Input: 4
4 2 5 2
Output: 9
2 4 5 6 7 8 9 11 13
Removal Game
CSES - Removal Game
Time limit: 1.00 s
Memory limit: 512 MB
There is a list of n numbers and two players who move alternately. On each move, a player removes either the first or last number from the list, and their score increases by that number. Both players try to maximize their scores.
What is the maximum possible score for the first player when both players play optimally?
Input
The first input line contains an integer n: the size of the list.
The next line has n integers x1,x2,…,xn: the contents of the list.
Output
Print the maximum possible score for the first player.
Constraints
1≤n≤5000
−109≤xi≤109
Example
Input: 4
4 5 1 3
Output: 8
Two Sets II
CSES - Two Sets II
Time limit: 1.00 s
Memory limit: 512 MB
Your task is to count the number of ways numbers 1,2,…,n can be divided into two sets of equal sum.
For example, if n=7, there are four solutions:
{1,3,4,6} and {2,5,7}
{1,2,5,6} and {3,4,7}
{1,2,4,7} and {3,5,6}
{1,6,7} and {2,3,4,5}
Input
The only input line contains an integer n.
Output
Print the answer modulo 109+7.
Constraints
1≤n≤500
Example
Input: 7
Output: 4
Increasing Subsequence
CSES - Increasing Subsequence
Time limit: 1.00 s
Memory limit: 512 MB
You are given an array containing n integers. Your task is to determine the longest increasing subsequence in the array, i.e., the longest subsequence where every element is larger than the previous one.
A subsequence is a sequence that can be derived from the array by deleting some elements without changing the order of the remaining elements.
Input
The first line contains an integer n: the size of the array.
After this there are n integers x1,x2,…,xn: the contents of the array.
Output
Print the length of the longest increasing subsequence.
Constraints
1≤n≤2⋅105
1≤xi≤109
Example
Input: 8
7 3 5 3 6 2 9 8
Output: 4
Increasing Subsequence
CSES - Increasing Subsequence
Time limit: 1.00 s
Memory limit: 512 MB
You are given an array containing n integers. Your task is to determine the longest increasing subsequence in the array, i.e., the longest subsequence where every element is larger than the previous one.
A subsequence is a sequence that can be derived from the array by deleting some elements without changing the order of the remaining elements.
Input
The first line contains an integer n: the size of the array.
After this there are n integers x1,x2,…,xn: the contents of the array.
Output
Print the length of the longest increasing subsequence.
Constraints
1≤n≤2⋅105
1≤xi≤109
Example
Input: 8
7 3 5 3 6 2 9 8
Output: 4
Increasing Subsquence
CSES - Increasing Subsequence
Time limit: 1.00 s
Memory limit: 512 MB
You are given an array containing n integers. Your task is to determine the longest increasing subsequence in the array, i.e., the longest subsequence where every element is larger than the previous one.
A subsequence is a sequence that can be derived from the array by deleting some elements without changing the order of the remaining elements.
Input
The first line contains an integer n: the size of the array.
After this there are n integers x1,x2,…,xn: the contents of the array.
Output
Print the length of the longest increasing subsequence.
Constraints
1≤n≤2⋅105
1≤xi≤109
Example
Input: 8
7 3 5 3 6 2 9 8
Output: 4
Projects
CSES - Projects
Time limit: 1.00 s
Memory limit: 512 MB
There are n projects you can attend. For each project, you know its starting and ending days and the amount of money you would get as reward. You can only attend one project during a day.
What is the maximum amount of money you can earn?
Input
The first input line contains an integer n: the number of projects.
After this, there are n lines. Each such line has three integers ai, bi, and pi: the starting day, the ending day, and the reward.
Output
Print one integer: the maximum amount of money you can earn.
Constraints
1≤n≤2⋅105
1≤ai≤bi≤109
1≤pi≤109
Example
Input: 4
2 4 4
3 6 6
6 8 2
5 7 3
Output: 7
Elevator Rides
CSES - Elevator Rides
Time limit: 1.00 s
Memory limit: 512 MB
There are n people who want to get to the top of a building which has only one elevator. You know the weight of each person and the maximum allowed weight in the elevator. What is the minimum number of elevator rides?
Input
The first input line has two integers n and x: the number of people and the maximum allowed weight in the elevator.
The second line has n integers w1,w2,…,wn: the weight of each person.
Output
Print one integer: the minimum number of rides.
Constraints
1≤n≤20
1≤x≤109
1≤wi≤x
Example
Input: 4 10
4 8 6 1
Output: 2
Counting Tilings
CSES - Counting Tilings
Time limit: 1.00 s
Memory limit: 512 MB
Your task is to count the number of ways you can fill an n×m grid using 1×2 and 2×1 tiles.
Input
The only input line has two integers n and m.
Output
Print one integer: the number of ways modulo 109+7.
Constraints
1≤n≤10
1≤m≤1000
Example
Input: 4 7
Output: 781
Counting Numbers
CSES - Counting Numbers
Time limit: 1.00 s
Memory limit: 512 MB
Your task is to count the number of integers between a and b where no two adjacent digits are the same.
Input
The only input line has two integers a and b.
Output
Print one integer: the answer to the problem.
Constraints
0≤a≤b≤1018
Example
Input: 123 321
Output: 171
Graph Algorithms
Counting Rooms
CSES - Counting Rooms
Time limit: 1.00 s
Memory limit: 512 MB
You are given a map of a building, and your task is to count the number of its rooms. The size of the map is n×m squares, and each square is either floor or wall. You can walk left, right, up, and down through the floor squares.
Input
The first input line has two integers n and m: the height and width of the map.
Then there are n lines of m characters describing the map. Each character is either . (floor) or # (wall).
You are given a map of a labyrinth, and your task is to find a path from start to end. You can walk left, right, up and down.
Input
The first input line has two integers n and m: the height and width of the map.
Then there are n lines of m characters describing the labyrinth. Each character is . (floor), # (wall), A (start), or B (end). There is exactly one A and one B in the input.
Output
First print "YES", if there is a path, and "NO" otherwise.
If there is a path, print the length of the shortest such path and its description as a string consisting of characters L (left), R (right), U (up), and D (down). You can print any valid solution.
Byteland has n cities, and m roads between them. The goal is to construct new roads so that there is a route between any two cities.
Your task is to find out the minimum number of roads required, and also determine which roads should be built.
Input
The first input line has two integers n and m: the number of cities and roads. The cities are numbered 1,2,…,n.
After that, there are m lines describing the roads. Each line has two integers a and b: there is a road between those cities.
A road always connects two different cities, and there is at most one road between any two cities.
Output
First print an integer k: the number of required roads.
Then, print k lines that describe the new roads. You can print any valid solution.
Constraints
1≤n≤105
1≤m≤2⋅105
1≤a,b≤n
Example
Input: 4 2
1 2
3 4
Output: 1
2 3
Message Route
CSES - Message Route
Time limit: 1.00 s
Memory limit: 512 MB
Syrjälä's network has n computers and m connections. Your task is to find out if Uolevi can send a message to Maija, and if it is possible, what is the minimum number of computers on such a route.
Input
The first input line has two integers n and m: the number of computers and connections. The computers are numbered 1,2,…,n. Uolevi's computer is 1 and Maija's computer is n.
Then, there are m lines describing the connections. Each line has two integers a and b: there is a connection between those computers.
Every connection is between two different computers, and there is at most one connection between any two computers.
Output
If it is possible to send a message, first print k: the minimum number of computers on a valid route. After this, print an example of such a route. You can print any valid solution.
If there are no routes, print "IMPOSSIBLE".
Constraints
2≤n≤105
1≤m≤2⋅105
1≤a,b≤n
Example
Input: 5 5
1 2
1 3
1 4
2 3
5 4
Output: 3
1 4 5
Building Teams
CSES - Building Teams
Time limit: 1.00 s
Memory limit: 512 MB
There are n pupils in Uolevi's class, and m friendships between them. Your task is to divide the pupils into two teams in such a way that no two pupils in a team are friends. You can freely choose the sizes of the teams.
Input
The first input line has two integers n and m: the number of pupils and friendships. The pupils are numbered 1,2,…,n.
Then, there are m lines describing the friendships. Each line has two integers a and b: pupils a and b are friends.
Every friendship is between two different pupils. You can assume that there is at most one friendship between any two pupils.
Output
Print an example of how to build the teams. For each pupil, print "1" or "2" depending on to which team the pupil will be assigned. You can print any valid team.
If there are no solutions, print "IMPOSSIBLE".
Constraints
1≤n≤105
1≤m≤2⋅105
1≤a,b≤n
Example
Input: 5 3
1 2
1 3
4 5
Output: 1 2 2 1 2
Round Trip
CSES - Round Trip
Time limit: 1.00 s
Memory limit: 512 MB
Byteland has n cities and m roads between them. Your task is to design a round trip that begins in a city, goes through two or more other cities, and finally returns to the starting city. Every intermediate city on the route has to be distinct.
Input
The first input line has two integers n and m: the number of cities and roads. The cities are numbered 1,2,…,n.
Then, there are m lines describing the roads. Each line has two integers a and b: there is a road between those cities.
Every road is between two different cities, and there is at most one road between any two cities.
Output
First print an integer k: the number of cities on the route. Then print k cities in the order they will be visited. You can print any valid solution.
If there are no solutions, print "IMPOSSIBLE".
Constraints
1≤n≤105
1≤m≤2⋅105
1≤a,b≤n
Example
Input: 5 6
1 3
1 2
5 3
1 5
2 4
4 5
Output: 4
3 5 1 3
Monsters
CSES - Monsters
Time limit: 1.00 s
Memory limit: 512 MB
You and some monsters are in a labyrinth. When taking a step to some direction in the labyrinth, each monster may simultaneously take one as well. Your goal is to reach one of the boundary squares without ever sharing a square with a monster.
Your task is to find out if your goal is possible, and if it is, print a path that you can follow. Your plan has to work in any situation; even if the monsters know your path beforehand.
Input
The first input line has two integers n and m: the height and width of the map.
After this there are n lines of m characters describing the map. Each character is . (floor), # (wall), A (start), or M (monster). There is exactly one A in the input.
Output
First print "YES" if your goal is possible, and "NO" otherwise.
If your goal is possible, also print an example of a valid path (the length of the path and its description using characters D, U, L, and R). You can print any path, as long as its length is at most n⋅m steps.
There are n cities and m flight connections between them. Your task is to determine the length of the shortest route from Syrjälä to every city.
Input
The first input line has two integers n and m: the number of cities and flight connections. The cities are numbered 1,2,…,n, and city 1 is Syrjälä.
After that, there are m lines describing the flight connections. Each line has three integers a, b and c: a flight begins at city a, ends at city b, and its length is c. Each flight is a one-way flight.
You can assume that it is possible to travel from Syrjälä to all other cities.
Output
Print n integers: the shortest route lengths from Syrjälä to cities 1,2,…,n.
Constraints
1≤n≤105
1≤m≤2⋅105
1≤a,b≤n
1≤c≤109
Example
Input: 3 4
1 2 6
1 3 2
3 2 3
1 3 4
Output: 0 5 2
Shortest Routes II
CSES - Shortest Routes II
Time limit: 1.00 s
Memory limit: 512 MB
There are n cities and m roads between them. Your task is to process q queries where you have to determine the length of the shortest route between two given cities.
Input
The first input line has three integers n, m and q: the number of cities, roads, and queries.
Then, there are m lines describing the roads. Each line has three integers a, b and c: there is a road between cities a and b whose length is c. All roads are two-way roads.
Finally, there are q lines describing the queries. Each line has two integers a and b: determine the length of the shortest route between cities a and b.
Output
Print the length of the shortest route for each query. If there is no route, print −1 instead.
You play a game consisting of n rooms and m tunnels. Your initial score is 0, and each tunnel increases your score by x where x may be both positive or negative. You may go through a tunnel several times.
Your task is to walk from room 1 to room n. What is the maximum score you can get?
Input
The first input line has two integers n and m: the number of rooms and tunnels. The rooms are numbered 1,2,…,n.
Then, there are m lines describing the tunnels. Each line has three integers a, b and x: the tunnel starts at room a, ends at room b, and it increases your score by x. All tunnels are one-way tunnels.
You can assume that it is possible to get from room 1 to room n.
Output
Print one integer: the maximum score you can get. However, if you can get an arbitrarily large score, print −1.
Constraints
1≤n≤2500
1≤m≤5000
1≤a,b≤n
−109≤x≤109
Example
Input: 4 5
1 2 3
2 4 -1
1 3 -2
3 4 7
1 4 4
Output: 5
Flight Discount
CSES - Flight Discount
Time limit: 1.00 s
Memory limit: 512 MB
Your task is to find a minimum-price flight route from Syrjälä to Metsälä. You have one discount coupon, using which you can halve the price of any single flight during the route. However, you can only use the coupon once.
Input
The first input line has two integers n and m: the number of cities and flight connections. The cities are numbered 1,2,…,n. City 1 is Syrjälä, and city n is Metsälä.
After this there are m lines describing the flights. Each line has three integers a, b, and c: a flight begins at city a, ends at city b, and its price is c. Each flight is unidirectional.
You can assume that it is always possible to get from Syrjälä to Metsälä.
Output
Print one integer: the price of the cheapest route from Syrjälä to Metsälä.
When you use the discount coupon for a flight whose price is x, its price becomes ⌊x/2⌋ (it is rounded down to an integer).
Constraints
2≤n≤105
1≤m≤2⋅105
1≤a,b≤n
1≤c≤109
Example
Input: 3 4
1 2 3
2 3 1
1 3 7
2 1 5
Output: 2
Circle Finding
CSES - Flight Discount
Time limit: 1.00 s
Memory limit: 512 MB
Your task is to find a minimum-price flight route from Syrjälä to Metsälä. You have one discount coupon, using which you can halve the price of any single flight during the route. However, you can only use the coupon once.
Input
The first input line has two integers n and m: the number of cities and flight connections. The cities are numbered 1,2,…,n. City 1 is Syrjälä, and city n is Metsälä.
After this there are m lines describing the flights. Each line has three integers a, b, and c: a flight begins at city a, ends at city b, and its price is c. Each flight is unidirectional.
You can assume that it is always possible to get from Syrjälä to Metsälä.
Output
Print one integer: the price of the cheapest route from Syrjälä to Metsälä.
When you use the discount coupon for a flight whose price is x, its price becomes ⌊x/2⌋ (it is rounded down to an integer).
Constraints
2≤n≤105
1≤m≤2⋅105
1≤a,b≤n
1≤c≤109
Example
Input: 3 4
1 2 3
2 3 1
1 3 7
2 1 5
Output: 2
Round Trip II
CSES - Round Trip II
Time limit: 1.00 s
Memory limit: 512 MB
Byteland has n cities and m flight connections. Your task is to design a round trip that begins in a city, goes through one or more other cities, and finally returns to the starting city. Every intermediate city on the route has to be distinct.
Input
The first input line has two integers n and m: the number of cities and flights. The cities are numbered 1,2,…,n.
Then, there are m lines describing the flights. Each line has two integers a and b: there is a flight connection from city a to city b. All connections are one-way flights from a city to another city.
Output
First print an integer k: the number of cities on the route. Then print k cities in the order they will be visited. You can print any valid solution.
If there are no solutions, print "IMPOSSIBLE".
Constraints
1≤n≤105
1≤m≤2⋅105
1≤a,b≤n
Example
Input: 4 5
1 3
2 1
2 4
3 2
3 4
Output: 4
2 1 3 2
Course Schedule
CSES - Course Schedule
Time limit: 1.00 s
Memory limit: 512 MB
You have to complete n courses. There are m requirements of the form "course a has to be completed before course b". Your task is to find an order in which you can complete the courses.
Input
The first input line has two integers n and m: the number of courses and requirements. The courses are numbered 1,2,…,n.
After this, there are m lines describing the requirements. Each line has two integers a and b: course a has to be completed before course b.
Output
Print an order in which you can complete the courses. You can print any valid order that includes all the courses.
If there are no solutions, print "IMPOSSIBLE".
Constraints
1≤n≤105
1≤m≤2⋅105
1≤a,b≤n
Example
Input: 5 3
1 2
3 1
4 5
Output: 3 4 1 5 2
LOngest Flight Route
CSES - Longest Flight Route
Time limit: 1.00 s
Memory limit: 512 MB
Uolevi has won a contest, and the prize is a free flight trip that can consist of one or more flights through cities. Of course, Uolevi wants to choose a trip that has as many cities as possible.
Uolevi wants to fly from Syrjälä to Lehmälä so that he visits the maximum number of cities. You are given the list of possible flights, and you know that there are no directed cycles in the flight network.
Input
The first input line has two integers n and m: the number of cities and flights. The cities are numbered 1,2,…,n. City 1 is Syrjälä, and city n is Lehmälä.
After this, there are m lines describing the flights. Each line has two integers a and b: there is a flight from city a to city b. Each flight is a one-way flight.
Output
First print the maximum number of cities on the route. After this, print the cities in the order they will be visited. You can print any valid solution.
If there are no solutions, print "IMPOSSIBLE".
Constraints
2≤n≤105
1≤m≤2⋅105
1≤a,b≤n
Example
Input: 5 5
1 2
2 5
1 3
3 4
4 5
Output: 4
1 3 4 5
Game Routes
CSES - Game Routes
Time limit: 1.00 s
Memory limit: 512 MB
A game has n levels, connected by m teleporters, and your task is to get from level 1 to level n. The game has been designed so that there are no directed cycles in the underlying graph. In how many ways can you complete the game?
Input
The first input line has two integers n and m: the number of levels and teleporters. The levels are numbered 1,2,…,n.
After this, there are m lines describing the teleporters. Each line has two integers a and b: there is a teleporter from level a to level b.
Output
Print one integer: the number of ways you can complete the game. Since the result may be large, print it modulo 109+7.
Constraints
1≤n≤105
1≤m≤2⋅105
1≤a,b≤n
Example
Input: 4 5
1 2
2 4
1 3
3 4
1 4
Output: 3
Investigation
CSES - Investigation
Time limit: 1.00 s
Memory limit: 512 MB
You are going to travel from Syrjälä to Lehmälä by plane. You would like to find answers to the following questions:
what is the minimum price of such a route?
how many minimum-price routes are there? (modulo 109+7)
what is the minimum number of flights in a minimum-price route?
what is the maximum number of flights in a minimum-price route?
Input
The first input line contains two integers n and m: the number of cities and the number of flights. The cities are numbered 1,2,…,n. City 1 is Syrjälä, and city n is Lehmälä.
After this, there are m lines describing the flights. Each line has three integers a, b, and c: there is a flight from city a to city b with price c. All flights are one-way flights.
You may assume that there is a route from Syrjälä to Lehmälä.
Output
Print four integers according to the problem statement.
Constraints
1≤n≤105
1≤m≤2⋅105
1≤a,b≤n
1≤c≤109
Example
Input: 4 5
1 4 5
1 2 4
2 4 5
1 3 2
3 4 3
Output: 5 2 1 2
PLanet Queries I
CSES - Planets Queries I
Time limit: 1.00 s
Memory limit: 512 MB
You are playing a game consisting of n planets. Each planet has a teleporter to another planet (or the planet itself).
Your task is to process q queries of the form: when you begin on planet x and travel through k teleporters, which planet will you reach?
Input
The first input line has two integers n and q: the number of planets and queries. The planets are numbered 1,2,…,n.
The second line has n integers t1,t2,…,tn: for each planet, the destination of the teleporter. It is possible that ti=i.
Finally, there are q lines describing the queries. Each line has two integers x and k: you start on planet x and travel through k teleporters.
Output
Print the answer to each query.
Constraints
1≤n,q≤2⋅105
1≤ti≤n
1≤x≤n
0≤k≤109
Example
Input: 4 3
2 1 1 4
1 2
3 4
4 1
Output: 1
2
4
Planet Queries II
CSES - Planets Queries II
Time limit: 1.00 s
Memory limit: 512 MB
You are playing a game consisting of n planets. Each planet has a teleporter to another planet (or the planet itself).
You have to process q queries of the form: You are now on planet a and want to reach planet b. What is the minimum number of teleportations?
Input
The first input line contains two integers n and q: the number of planets and queries. The planets are numbered 1,2,…,n.
The second line contains n integers t1,t2,…,tn: for each planet, the destination of the teleporter.
Finally, there are q lines describing the queries. Each line has two integers a and b: you are now on planet a and want to reach planet b.
Output
For each query, print the minimum number of teleportations. If it is not possible to reach the destination, print −1.
Constraints
1≤n,q≤2⋅105
1≤a,b≤n
Example
Input: 5 3
2 3 2 3 2
1 2
1 3
1 4
Output: 1
2
-1
Planet Cycles
CSES - Planets Cycles
Time limit: 1.00 s
Memory limit: 512 MB
You are playing a game consisting of n planets. Each planet has a teleporter to another planet (or the planet itself).
You start on a planet and then travel through teleporters until you reach a planet that you have already visited before.
Your task is to calculate for each planet the number of teleportations there would be if you started on that planet.
Input
The first input line has an integer n: the number of planets. The planets are numbered 1,2,…,n.
The second line has n integers t1,t2,…,tn: for each planet, the destination of the teleporter. It is possible that ti=i.
Output
Print n integers according to the problem statement.
Constraints
1≤n≤2⋅105
1≤ti≤n
Example
Input: 5
2 4 3 1 4
Output: 3 3 1 3 4
Road Reparation
CSES - Road Reparation
Time limit: 1.00 s
Memory limit: 128 MB
There are n cities and m roads between them. Unfortunately, the condition of the roads is so poor that they cannot be used. Your task is to repair some of the roads so that there will be a decent route between any two cities.
For each road, you know its reparation cost, and you should find a solution where the total cost is as small as possible.
Input
The first input line has two integers n and m: the number of cities and roads. The cities are numbered 1,2,…,n.
Then, there are m lines describing the roads. Each line has three integers a, b and c: there is a road between cities a and b, and its reparation cost is c. All roads are two-way roads.
Every road is between two different cities, and there is at most one road between two cities.
Output
Print one integer: the minimum total reparation cost. However, if there are no solutions, print "IMPOSSIBLE".
Constraints
1≤n≤105
1≤m≤2⋅105
1≤a,b≤n
1≤c≤109
Example
Input: 5 6
1 2 3
2 3 5
2 4 2
3 4 8
5 1 7
5 4 4
Output: 14
Road Construction
CSES - Road Construction
Time limit: 1.00 s
Memory limit: 512 MB
There are n cities and initially no roads between them. However, every day a new road will be constructed, and there will be a total of m roads.
A component is a group of cities where there is a route between any two cities using the roads. After each day, your task is to find the number of components and the size of the largest component.
Input
The first input line has two integers n and m: the number of cities and roads. The cities are numbered 1,2,…,n.
Then, there are m lines describing the new roads. Each line has two integers a and b: a new road is constructed between cities a and b.
You may assume that every road will be constructed between two different cities.
Output
Print m lines: the required information after each day.
Constraints
1≤n≤105
1≤m≤2⋅105
1≤a,b≤n
Example
Input: 5 3
1 2
1 3
4 5
Output: 4 2
3 3
2 3
Flight Routes Checks
CSES - Flight Routes Check
Time limit: 1.00 s
Memory limit: 512 MB
There are n cities and m flight connections. Your task is to check if you can travel from any city to any other city using the available flights.
Input
The first input line has two integers n and m: the number of cities and flights. The cities are numbered 1,2,…,n.
After this, there are m lines describing the flights. Each line has two integers a and b: there is a flight from city a to city b. All flights are one-way flights.
Output
Print "YES" if all routes are possible, and "NO" otherwise. In the latter case also print two cities a and b such that you cannot travel from city a to city b.
Constraints
1≤n≤105
1≤m≤2⋅105
1≤a,b≤n
Example
Input: 4 5
1 2
2 3
3 1
1 4
3 4
Output: NO
4 2
Planets and Kingdoms
CSES - Planets and Kingdoms
Time limit: 1.00 s
Memory limit: 512 MB
A game has n planets, connected by m teleporters. Two planets a and b belong to the same kingdom exactly when there is a route both from a to b and from b to a. Your task is to determine for each planet its kingdom.
Input
The first input line has two integers n and m: the number of planets and teleporters. The planets are numbered 1,2,…,n.
After this, there are m lines describing the teleporters. Each line has two integers a and b: you can travel from planet a to planet b through a teleporter.
Output
First print an integer k: the number of kingdoms. After this, print for each planet a kingdom label between 1 and k. You can print any valid solution.
Constraints
1≤n≤105
1≤m≤2⋅105
1≤a,b≤n
Example
Input: 5 6
1 2
2 3
3 1
3 4
4 5
5 4
Output: 2
1 1 1 2 2
Giant Pizza
CSES - Giant Pizza
Time limit: 1.00 s
Memory limit: 512 MB
Uolevi's family is going to order a large pizza and eat it together. A total of n family members will join the order, and there are m possible toppings. The pizza may have any number of toppings.
Each family member gives two wishes concerning the toppings of the pizza. The wishes are of the form "topping x is good/bad". Your task is to choose the toppings so that at least one wish from everybody becomes true (a good topping is included in the pizza or a bad topping is not included).
Input
The first input line has two integers n and m: the number of family members and toppings. The toppings are numbered 1,2,…,m.
After this, there are n lines describing the wishes. Each line has two wishes of the form "+ x" (topping x is good) or "- x" (topping x is bad).
Output
Print a line with m symbols: for each topping "+" if it is included and "-" if it is not included. You can print any valid solution.
If there are no valid solutions, print "IMPOSSIBLE".
Constraints
1≤n,m≤105
1≤x≤m
Example
Input: 3 5
+ 1 + 2
- 1 + 3
+ 4 - 2
Output: - + + + -
Coin Collector
CSES - Coin Collector
Time limit: 1.00 s
Memory limit: 512 MB
A game has n rooms and m tunnels between them. Each room has a certain number of coins. What is the maximum number of coins you can collect while moving through the tunnels when you can freely choose your starting and ending room?
Input
The first input line has two integers n and m: the number of rooms and tunnels. The rooms are numbered 1,2,…,n.
Then, there are n integers k1,k2,…,kn: the number of coins in each room.
Finally, there are m lines describing the tunnels. Each line has two integers a and b: there is a tunnel from room a to room b. Each tunnel is a one-way tunnel.
Output
Print one integer: the maximum number of coins you can collect.
Constraints
1≤n≤105
1≤m≤2⋅105
1≤ki≤109
1≤a,b≤n
Example
Input: 4 4
4 5 2 7
1 2
2 1
1 3
2 4
Output: 16
Mail Delivery
CSES - Mail Delivery
Time limit: 1.00 s
Memory limit: 512 MB
Your task is to deliver mail to the inhabitants of a city. For this reason, you want to find a route whose starting and ending point are the post office, and that goes through every street exactly once.
Input
The first input line has two integers n and m: the number of crossings and streets. The crossings are numbered 1,2,…,n, and the post office is located at crossing 1.
After that, there are m lines describing the streets. Each line has two integers a and b: there is a street between crossings a and b. All streets are two-way streets.
Every street is between two different crossings, and there is at most one street between two crossings.
Output
Print all the crossings on the route in the order you will visit them. You can print any valid solution.
If there are no solutions, print "IMPOSSIBLE".
Constraints
2≤n≤105 1≤m≤2.105 1≤a,b≤n
Example
Input:
6 8
1 2
1 3
2 3
2 4
2 6
3 5
3 6
4 5
Output: 1 2 6 3 2 4 5 3 1
De Bruijn Sequence
CSES - De Bruijn Sequence
Time limit: 1.00 s
Memory limit: 512 MB
Your task is to construct a minimum-length bit string that contains all possible substrings of length n. For example, when n=2, the string 00110 is a valid solution, because its substrings of length 2 are 00, 01, 10 and 11.
Input
The only input line has an integer n.
Output
Print a minimum-length bit string that contains all substrings of length n. You can print any valid solution.
Constraints
1≤n≤15
Example
Input: 2
Output: 00110
Teleporters Path
CSES - Teleporters Path
Time limit: 1.00 s
Memory limit: 512 MB
A game has n levels and m teleportes between them. You win the game if you move from level 1 to level n using every teleporter exactly once.
Can you win the game, and what is a possible way to do it?
Input
The first input line has two integers n and m: the number of levels and teleporters. The levels are numbered 1,2,…,n.
Then, there are m lines describing the teleporters. Each line has two integers a and b: there is a teleporter from level a to level b.
You can assume that each pair (a,b) in the input is distinct.
Output
Print m+1 integers: the sequence in which you visit the levels during the game. You can print any valid solution.
If there are no solutions, print "IMPOSSIBLE".
Constraints
2≤n≤105
1≤m≤2⋅105
1≤a,b≤n
Example
Input: 5 6
1 2
1 3
2 4
2 5
3 1
4 2
Output: 1 3 1 2 4 2 5
Hamiltonian Flights
CSES - Hamiltonian Flights
Time limit: 1.00 s
Memory limit: 512 MB
There are n cities and m flight connections between them. You want to travel from Syrjälä to Lehmälä so that you visit each city exactly once. How many possible routes are there?
Input
The first input line has two integers n and m: the number of cities and flights. The cities are numbered 1,2,…,n. City 1 is Syrjälä, and city n is Lehmälä.
Then, there are m lines describing the flights. Each line has two integers a and b: there is a flight from city a to city b. All flights are one-way flights.
Output
Print one integer: the number of routes modulo 109+7.
Constraints
2≤n≤20
1≤m≤n2
1≤a,b≤n
Example
Input: 4 6
1 2
1 3
2 3
3 2
2 4
3 4
Output: 2
Knight's Tour
CSES - Knight's Tour
Time limit: 1.00 s
Memory limit: 512 MB
Given a starting position of a knight on an 8×8 chessboard, your task is to find a sequence of moves such that it visits every square exactly once.
On each move, the knight may either move two steps horizontally and one step vertically, or one step horizontally and two steps vertically.
Input
The only line has two integers x and y: the knight's starting position.
Output
Print a grid that shows how the knight moves (according to the example). You can print any valid solution.
Consider a network consisting of n computers and m connections. Each connection specifies how fast a computer can send data to another computer.
Kotivalo wants to download some data from a server. What is the maximum speed he can do this, using the connections in the network?
Input
The first input line has two integers n and m: the number of computers and connections. The computers are numbered 1,2,…,n. Computer 1 is the server and computer n is Kotivalo's computer.
After this, there are m lines describing the connections. Each line has three integers a, b and c: computer a can send data to computer b at speed c.
Output
Print one integer: the maximum speed Kotivalo can download data.
Constraints
1≤n≤500
1≤m≤1000
1≤a,b≤n
1≤c≤109
Example
Input: 4 5
1 2 3
2 4 2
1 3 4
3 4 5
4 1 3
Output: 6
Police Chase
CSES - Download Speed
Time limit: 1.00 s
Memory limit: 512 MB
Consider a network consisting of n computers and m connections. Each connection specifies how fast a computer can send data to another computer.
Kotivalo wants to download some data from a server. What is the maximum speed he can do this, using the connections in the network?
Input
The first input line has two integers n and m: the number of computers and connections. The computers are numbered 1,2,…,n. Computer 1 is the server and computer n is Kotivalo's computer.
After this, there are m lines describing the connections. Each line has three integers a, b and c: computer a can send data to computer b at speed c.
Output
Print one integer: the maximum speed Kotivalo can download data.
Constraints
1≤n≤500
1≤m≤1000
1≤a,b≤n
1≤c≤109
Example
Input: 4 5
1 2 3
2 4 2
1 3 4
3 4 5
4 1 3
Output: 6
School Dance
CSES - School Dance
Time limit: 1.00 s
Memory limit: 512 MB
There are n boys and m girls in a school. Next week a school dance will be organized. A dance pair consists of a boy and a girl, and there are k potential pairs.
Your task is to find out the maximum number of dance pairs and show how this number can be achieved.
Input
The first input line has three integers n, m and k: the number of boys, girls, and potential pairs. The boys are numbered 1,2,…,n, and the girls are numbered 1,2,…,m.
After this, there are k lines describing the potential pairs. Each line has two integers a and b: boy a and girl b are willing to dance together.
Output
First print one integer r: the maximum number of dance pairs. After this, print r lines describing the pairs. You can print any valid solution.
Constraints
1≤n,m≤500
1≤k≤1000
1≤a≤n
1≤b≤m
Example
Input: 3 2 4
1 1
1 2
2 1
3 1
Output: 2
1 2
3 1
Distinct Routes
CSES - Distinct Routes
Time limit: 1.00 s
Memory limit: 512 MB
A game consists of n rooms and m teleporters. At the beginning of each day, you start in room 1 and you have to reach room n.
You can use each teleporter at most once during the game. How many days can you play if you choose your routes optimally?
Input
The first input line has two integers n and m: the number of rooms and teleporters. The rooms are numbered 1,2,…,n.
After this, there are m lines describing the teleporters. Each line has two integers a and b: there is a teleporter from room a to room b.
There are no two teleporters whose starting and ending room are the same.
Output
First print an integer k: the maximum number of days you can play the game. Then, print k route descriptions according to the example. You can print any valid solution.
Constraints
2≤n≤500
1≤m≤1000
1≤a,b≤n
Example
Input: 6 7
1 2
1 3
2 6
3 4
3 5
4 6
5 6
Output: 2
3
1 2 6
4
1 3 4 6
Static Range Sum Queries
CSES - Static Range Sum Queries
Time limit: 1.00 s
Memory limit: 512 MB
Given an array of n integers, your task is to process q queries of the form: what is the sum of values in range [a,b]?
Input
The first input line has two integers n and q: the number of values and queries.
The second line has n integers x1,x2,…,xn: the array values.
Finally, there are q lines describing the queries. Each line has two integers a and b: what is the sum of values in range [a,b]?
Output
Print the result of each query.
Constraints
1≤n,q≤2⋅105
1≤xi≤109
1≤a≤b≤n
Example
Input: 8 4
3 2 4 5 1 1 5 3
2 4
5 6
1 8
3 3
Output: 11
2
24
4
Static Range Minimum Queries
CSES - Static Range Minimum Queries
Time limit: 1.00 s
Memory limit: 512 MB
Given an array of n integers, your task is to process q queries of the form: what is the minimum value in range [a,b]?
Input
The first input line has two integers n and q: the number of values and queries.
The second line has n integers x1,x2,…,xn: the array values.
Finally, there are q lines describing the queries. Each line has two integers a and b: what is the minimum value in range [a,b]?
Output
Print the result of each query.
Constraints
1≤n,q≤2⋅105
1≤xi≤109
1≤a≤b≤n
Example
Input: 8 4
3 2 4 5 1 1 5 3
2 4
5 6
1 8
3 3
Output: 2
1
1
4
Dynamic Range Sum Queries
CSES - Dynamic Range Sum Queries
Time limit: 1.00 s
Memory limit: 512 MB
Given an array of n integers, your task is to process q queries of the following types:
update the value at position k to u
what is the sum of values in range [a,b]?
Input
The first input line has two integers n and q: the number of values and queries.
The second line has n integers x1,x2,…,xn: the array values.
Finally, there are q lines describing the queries. Each line has three integers: either "1ku" or "2ab".
Given an array of n integers, your task is to process q queries of the form: what is the xor sum of values in range [a,b]?
Input
The first input line has two integers n and q: the number of values and queries.
The second line has n integers x1,x2,…,xn: the array values.
Finally, there are q lines describing the queries. Each line has two integers a and b: what is the xor sum of values in range [a,b]?
Output
Print the result of each query.
Constraints
1≤n,q≤2⋅105
1≤xi≤109
1≤a≤b≤n
Example
Input: 8 4
3 2 4 5 1 1 5 3
2 4
5 6
1 8
3 3
Output: 3
0
6
4
Range Update Queries
CSES - Range Update Queries
Time limit: 1.00 s
Memory limit: 512 MB
Given an array of n integers, your task is to process q queries of the following types:
increase each value in range [a,b] by u
what is the value at position k?
Input
The first input line has two integers n and q: the number of values and queries.
The second line has n integers x1,x2,…,xn: the array values.
Finally, there are q lines describing the queries. Each line has three integers: either "1abu" or "2k".
Output
Print the result of each query of type 2.
Constraints
1≤n,q≤2⋅105
1≤xi,u≤109
1≤k≤n
1≤a≤b≤n
Example
Input: 8 3
3 2 4 5 1 1 5 3
2 4
1 2 5 1
2 4
Output: 5
6
Forest Queries
CSES - Forest Queries
Time limit: 1.00 s
Memory limit: 512 MB
You are given an n×n grid representing the map of a forest. Each square is either empty or contains a tree. The upper-left square has coordinates (1,1), and the lower-right square has coordinates (n,n).
Your task is to process q queries of the form: how many trees are inside a given rectangle in the forest?
Input
The first input line has two integers n and q: the size of the forest and the number of queries.
Then, there are n lines describing the forest. Each line has n characters: . is an empty square and * is a tree.
Finally, there are q lines describing the queries. Each line has four integers y1, x1, y2, x2 corresponding to the corners of a rectangle.
There are n hotels on a street. For each hotel you know the number of free rooms. Your task is to assign hotel rooms for groups of tourists. All members of a group want to stay in the same hotel.
The groups will come to you one after another, and you know for each group the number of rooms it requires. You always assign a group to the first hotel having enough rooms. After this, the number of free rooms in the hotel decreases.
Input
The first input line contains two integers n and m: the number of hotels and the number of groups. The hotels are numbered 1,2,…,n.
The next line contains n integers h1,h2,…,hn: the number of free rooms in each hotel.
The last line contains m integers r1,r2,…,rm: the number of rooms each group requires.
Output
Print the assigned hotel for each group. If a group cannot be assigned a hotel, print 0 instead.
Constraints
1≤n,m≤2⋅105
1≤hi≤109
1≤ri≤109
Example
Input: 8 5
3 2 4 1 5 5 2 6
4 4 7 1 1
Output: 3 5 0 1 1
List Removals
CSES - List Removals
Time limit: 1.00 s
Memory limit: 512 MB
You are given a list consisting of n integers. Your task is to remove elements from the list at given positions, and report the removed elements.
Input
The first input line has an integer n: the initial size of the list. During the process, the elements are numbered 1,2,…,k where k is the current size of the list.
The second line has n integers x1,x2,…,xn: the contents of the list.
The last line has n integers p1,p2,…,pn: the positions of the elements to be removed.
Output
Print the elements in the order they are removed.
Constraints
1≤n≤2⋅105
1≤xi≤109
1≤pi≤n−i+1
Example
Input: 5
2 6 1 4 2
3 1 3 1 1
Output: 1 2 2 6 4
Explanation: The contents of the list are [2,6,1,4,2], [2,6,4,2], [6,4,2], [6,4], [4] and [].
Salary Queries
CSES - Salary Queries
Time limit: 1.00 s
Memory limit: 512 MB
A company has n employees with certain salaries. Your task is to keep track of the salaries and process queries.
Input
The first input line contains two integers n and q: the number of employees and queries. The employees are numbered 1,2,…,n.
The next line has n integers p1,p2,…,pn: each employee's salary.
After this, there are q lines describing the queries. Each line has one of the following forms:
!kx: change the salary of employee k to x
?ab: count the number of employees whose salary is between a…b
Output
Print the answer to each ? query.
Constraints
1≤n,q≤2⋅105
1≤pi≤109
1≤k≤n
1≤x≤109
1≤a≤b≤109
Example
Input: 5 3
3 7 2 2 5
? 2 3
! 3 6
? 2 3
Output: 3
2
Prefix Sum Queries
CSES - Prefix Sum Queries
Time limit: 1.00 s
Memory limit: 512 MB
Given an array of n integers, your task is to process q queries of the following types:
update the value at position k to u
what is the maximum prefix sum in range [a,b]?
Input
The first input line has two integers n and q: the number of values and queries.
The second line has n integers x1,x2,…,xn: the array values.
Finally, there are q lines describing the queries. Each line has three integers: either "1ku" or "2ab".
There are n buildings on a street, numbered 1,2,…,n. Each building has a pizzeria and an apartment.
The pizza price in building k is pk. If you order a pizza from building a to building b, its price (with delivery) is pa+|a−b|.
Your task is to process two types of queries:
The pizza price pk in building k becomes x.
You are in building k and want to order a pizza. What is the minimum price?
Input
The first input line has two integers n and q: the number of buildings and queries.
The second line has n integers p1,p2,…,pn: the initial pizza price in each building.
Finally, there are q lines that describe the queries. Each line is either "1 kx" or "2 k".
Output
Print the answer for each query of type 2.
Constraints
1≤n,q≤2⋅105
1≤pi,x≤109
1≤k≤n
Example
Input: 6 3
8 6 4 5 7 5
2 2
1 5 1
2 2
Output: 5
4
Subarray Sum Queries
CSES - Subarray Sum Queries
Time limit: 1.00 s
Memory limit: 512 MB
There is an array consisting of n integers. Some values of the array will be updated, and after each update, your task is to report the maximum subarray sum in the array.
Input
The first input line contains integers n and m: the size of the array and the number of updates. The array is indexed 1,2,…,n.
The next line has n integers: x1,x2,…,xn: the initial contents of the array.
Then there are m lines describing the changes. Each line has two integers k and x: the value at position k becomes x.
Output
After each update, print the maximum subarray sum. Empty subarrays (with sum 0) are allowed.
Constraints
1≤n,m≤2⋅105
−109≤xi≤109
1≤k≤n
−109≤x≤109
Example
Input: 5 3
1 2 -3 5 -1
2 6
3 1
2 -2
Output: 9
13
6
Distinct Values Queries
CSES - Distinct Values Queries
Time limit: 1.00 s
Memory limit: 512 MB
You are given an array of n integers and q queries of the form: how many distinct values are there in a range [a,b]?
Input
The first input line has two integers n and q: the array size and number of queries.
The next line has n integers x1,x2,…,xn: the array values.
Finally, there are q lines describing the queries. Each line has two integers a and b.
Output
For each query, print the number of distinct values in the range.
Constraints
1≤n,q≤2⋅105
1≤xi≤109
1≤a≤b≤n
Example
Input: 5 3
3 2 3 1 2
1 3
2 4
1 5
Output: 2
3
3
Increasing Array Queries
CSES - Increasing Array Queries
Time limit: 1.00 s
Memory limit: 512 MB
You are given an array that consists of n integers. The array elements are indexed 1,2,…,n.
You can modify the array using the following operation: choose an array element and increase its value by one.
Your task is to process q queries of the form: when we consider a subarray from position a to position b, what is the minimum number of operations after which the subarray is increasing?
An array is increasing if each element is greater than or equal with the previous element.
Input
The first input line has two integers n and q: the size of the array and the number of queries.
The next line has n integers x1,x2,…,xn: the contents of the array.
Finally, there are q lines that describe the queries. Each line has two integers a and b: the starting and ending position of a subarray.
Output
For each query, print the minimum number of operations.
Constraints
1≤n,q≤2⋅105
1≤xi≤109
1≤a≤b≤n
Example
Input: 5 3
2 10 4 2 5
3 5
2 2
1 4
Output: 2
0
14
Forest Queries II
CSES - Forest Queries II
Time limit: 1.00 s
Memory limit: 512 MB
You are given an n×n grid representing the map of a forest. Each square is either empty or has a tree. Your task is to process q queries of the following types:
Change the state (empty/tree) of a square.
How many trees are inside a rectangle in the forest?
Input
The first input line has two integers n and q: the size of the forest and the number of queries.
Then, there are n lines describing the forest. Each line has n characters: . is an empty square and * is a tree.
Finally, there are q lines describing the queries. The format of each line is either "1yx" or "2 y1x1y2x2".
Output
Print the answer to each query of the second type.
Given the structure of a company, your task is to calculate for each employee the number of their subordinates.
Input
The first input line has an integer n: the number of employees. The employees are numbered 1,2,…,n, and employee 1 is the general director of the company.
After this, there are n−1 integers: for each employee 2,3,…,n their direct boss in the company.
Output
Print n integers: for each employee 1,2,…,n the number of their subordinates.
Constraints
1≤n≤2⋅105
Example
Input: 5
1 1 2 3
Output: 4 1 1 0 0
CSES - Tree Matching
Time limit: 1.00 s
Memory limit: 512 MB
You are given a tree consisting of n nodes.
A matching is a set of edges where each node is an endpoint of at most one edge. What is the maximum number of edges in a matching?
Input
The first input line contains an integer n: the number of nodes. The nodes are numbered 1,2,…,n.
Then there are n−1 lines describing the edges. Each line contains two integers a and b: there is an edge between nodes a and b.
Output
Print one integer: the maximum number of pairs.
Constraints
1≤n≤2⋅105
1≤a,b≤n
Example
Input: 5
1 2
1 3
3 4
3 5
Output: 2
Explanation: One possible matching is (1,2) and (3,4).
Tree Diameter
CSES - Tree Diameter
Time limit: 1.00 s
Memory limit: 512 MB
You are given a tree consisting of n nodes.
The diameter of a tree is the maximum distance between two nodes. Your task is to determine the diameter of the tree.
Input
The first input line contains an integer n: the number of nodes. The nodes are numbered 1,2,…,n.
Then there are n−1 lines describing the edges. Each line contains two integers a and b: there is an edge between nodes a and b.
Output
Print one integer: the diameter of the tree.
Constraints
1≤n≤2⋅105
1≤a,b≤n
Example
Input: 5
1 2
1 3
3 4
3 5
Output: 3
Explanation: The diameter corresponds to the path 2→1→3→5.
Tree Distances I
CSES - Tree Distances I
Time limit: 1.00 s
Memory limit: 512 MB
You are given a tree consisting of n nodes.
Your task is to determine for each node the maximum distance to another node.
Input
The first input line contains an integer n: the number of nodes. The nodes are numbered 1,2,…,n.
Then there are n−1 lines describing the edges. Each line contains two integers a and b: there is an edge between nodes a and b.
Output
Print n integers: for each node 1,2,…,n, the maximum distance to another node.
Constraints
1≤n≤2⋅105
1≤a,b≤n
Example
Input: 5
1 2
1 3
3 4
3 5
Output: 2 3 2 3 3
Tree Distances II
CSES - Tree Distances II
Time limit: 1.00 s
Memory limit: 512 MB
You are given a tree consisting of n nodes.
Your task is to determine for each node the sum of the distances from the node to all other nodes.
Input
The first input line contains an integer n: the number of nodes. The nodes are numbered 1,2,…,n.
Then there are n−1 lines describing the edges. Each line contains two integers a and b: there is an edge between nodes a and b.
Output
Print n integers: for each node 1,2,…,n, the sum of the distances.
Constraints
1≤n≤2⋅105
1≤a,b≤n
Example
Input: 5
1 2
1 3
3 4
3 5
Output: 6 9 5 8 8
Company Queries I
CSES - Company Queries I
Time limit: 1.00 s
Memory limit: 512 MB
A company has n employees, who form a tree hierarchy where each employee has a boss, except for the general director.
Your task is to process q queries of the form: who is employee x's boss k levels higher up in the hierarchy?
Input
The first input line has two integers n and q: the number of employees and queries. The employees are numbered 1,2,…,n, and employee 1 is the general director.
The next line has n−1 integers e2,e3,…,en: for each employee 2,3,…,n their boss.
Finally, there are q lines describing the queries. Each line has two integers x and k: who is employee x's boss k levels higher up?
Output
Print the answer for each query. If such a boss does not exist, print −1.
Constraints
1≤n,q≤2⋅105
1≤ei≤i−1
1≤x≤n
1≤k≤n
Example
Input: 5 3
1 1 3 3
4 1
4 2
4 3
Output: 3
1
-1
Company Queries I
CSES - Company Queries I
Time limit: 1.00 s
Memory limit: 512 MB
A company has n employees, who form a tree hierarchy where each employee has a boss, except for the general director.
Your task is to process q queries of the form: who is employee x's boss k levels higher up in the hierarchy?
Input
The first input line has two integers n and q: the number of employees and queries. The employees are numbered 1,2,…,n, and employee 1 is the general director.
The next line has n−1 integers e2,e3,…,en: for each employee 2,3,…,n their boss.
Finally, there are q lines describing the queries. Each line has two integers x and k: who is employee x's boss k levels higher up?
Output
Print the answer for each query. If such a boss does not exist, print −1.
Constraints
1≤n,q≤2⋅105
1≤ei≤i−1
1≤x≤n
1≤k≤n
Example
Input: 5 3
1 1 3 3
4 1
4 2
4 3
Output: 3
1
-1
Company Queries II
CSES - Company Queries II
Time limit: 1.00 s
Memory limit: 512 MB
A company has n employees, who form a tree hierarchy where each employee has a boss, except for the general director.
Your task is to process q queries of the form: who is the lowest common boss of employees a and b in the hierarchy?
Input
The first input line has two integers n and q: the number of employees and queries. The employees are numbered 1,2,…,n, and employee 1 is the general director.
The next line has n−1 integers e2,e3,…,en: for each employee 2,3,…,n their boss.
Finally, there are q lines describing the queries. Each line has two integers a and b: who is the lowest common boss of employees a and b?
Output
Print the answer for each query.
Constraints
1≤n,q≤2⋅105
1≤ei≤i−1
1≤a,b≤n
Example
Input: 5 3
1 1 3 3
4 5
2 5
1 4
Output: 3
1
1
Distance Queries
CSES - Distance Queries
Time limit: 1.00 s
Memory limit: 512 MB
You are given a tree consisting of n nodes.
Your task is to process q queries of the form: what is the distance between nodes a and b?
Input
The first input line contains two integers n and q: the number of nodes and queries. The nodes are numbered 1,2,…,n.
Then there are n−1 lines describing the edges. Each line contains two integers a and b: there is an edge between nodes a and b.
Finally, there are q lines describing the queries. Each line contains two integer a and b: what is the distance between nodes a and b?
Output
Print q integers: the answer to each query.
Constraints
1≤n,q≤2⋅105
1≤a,b≤n
Example
Input: 5 3
1 2
1 3
3 4
3 5
1 3
2 5
1 4
Output: 1
3
2
Counting Paths
CSES - Counting Paths
Time limit: 1.00 s
Memory limit: 512 MB
You are given a tree consisting of n nodes, and m paths in the tree.
Your task is to calculate for each node the number of paths containing that node.
Input
The first input line contains integers n and m: the number of nodes and paths. The nodes are numbered 1,2,…,n.
Then there are n−1 lines describing the edges. Each line contains two integers a and b: there is an edge between nodes a and b.
Finally, there are m lines describing the paths. Each line contains two integers a and b: there is a path between nodes a and b.
Output
Print n integers: for each node 1,2,…,n, the number of paths containing that node.
Constraints
1≤n,m≤2⋅105
1≤a,b≤n
Example
Input: 5 3
1 2
1 3
3 4
3 5
1 3
2 5
1 4
Output: 3 1 3 1 1
Subtree Queries
CSES - Subtree Queries
Time limit: 1.00 s
Memory limit: 512 MB
You are given a rooted tree consisting of n nodes. The nodes are numbered 1,2,…,n, and node 1 is the root. Each node has a value.
Your task is to process following types of queries:
change the value of node s to x
calculate the sum of values in the subtree of node s
Input
The first input line contains two integers n and q: the number of nodes and queries. The nodes are numbered 1,2,…,n.
The next line has n integers v1,v2,…,vn: the value of each node.
Then there are n−1 lines describing the edges. Each line contans two integers a and b: there is an edge between nodes a and b.
Finally, there are q lines describing the queries. Each query is either of the form "1 sx" or "2 s".
You are given a rooted tree consisting of n nodes. The nodes are numbered 1,2,…,n, and node 1 is the root. Each node has a color.
Your task is to determine for each node the number of distinct colors in the subtree of the node.
Input
The first input line contains an integer n: the number of nodes. The nodes are numbered 1,2,…,n.
The next line consists of n integers c1,c2,…,cn: the color of each node.
Then there are n−1 lines describing the edges. Each line contains two integers a and b: there is an edge between nodes a and b.
Output
Print n integers: for each node 1,2,…,n, the number of distinct colors.
Constraints
1≤n≤2⋅105
1≤a,b≤n
1≤ci≤109
Example
Input: 5
2 3 2 2 1
1 2
1 3
3 4
3 5
Output: 3 1 2 1 1
Finding a Centroid
CSES - Finding a Centroid
Time limit: 1.00 s
Memory limit: 512 MB
Given a tree of n nodes, your task is to find a centroid, i.e., a node such that when it is appointed the root of the tree, each subtree has at most ⌊n/2⌋ nodes.
Input
The first input line contains an integer n: the number of nodes. The nodes are numbered 1,2,…,n.
Then there are n−1 lines describing the edges. Each line contains two integers a and b: there is an edge between nodes a and b.
Output
Print one integer: a centroid node. If there are several possibilities, you can choose any of them.
Constraints
1≤n≤2⋅105
1≤a,b≤n
Example
Input: 5
1 2
2 3
3 4
3 5
Output: 3
Fixed-Length Paths I
CSES - Fixed-Length Paths I
Time limit: 1.00 s
Memory limit: 512 MB
Given a tree of n nodes, your task is to count the number of distinct paths that consist of exactly k edges.
Input
The first input line contains two integers n and k: the number of nodes and the path length. The nodes are numbered 1,2,…,n.
Then there are n−1 lines describing the edges. Each line contains two integers a and b: there is an edge between nodes a and b.
Output
Print one integer: the number of paths.
Constraints
1≤k≤n≤2⋅105
1≤a,b≤n
Example
Input: 5 2
1 2
2 3
3 4
3 5
Output: 4
Fixed-Length Paths II
CSES - Fixed-Length Paths II
Time limit: 1.00 s
Memory limit: 512 MB
Given a tree of n nodes, your task is to count the number of distinct paths that have at least k1 and at most k2 edges.
Input
The first input line contains three integers n, k1 and k2: the number of nodes and the path lengths. The nodes are numbered 1,2,…,n.
Then there are n−1 lines describing the edges. Each line contains two integers a and b: there is an edge between nodes a and b.
Output
Print one integer: the number of paths.
Constraints
1≤k1≤k2≤n≤2⋅105
1≤a,b≤n
Example
Input: 5 2 3
1 2
2 3
3 4
3 5
Output: 6
Mathematics
Josephus Queries
CSES - Josephus Queries
Time limit: 1.00 s
Memory limit: 512 MB
Consider a game where there are n children (numbered 1,2,…,n) in a circle. During the game, every second child is removed from the circle, until there are no children left.
Your task is to process q queries of the form: "when there are n children, who is the kth child that will be removed?"
Input
The first input line has an integer q: the number of queries.
After this, there are q lines that describe the queries. Each line has two integers n and k: the number of children and the position of the child.
Output
Print q integers: the answer for each query.
Constraints
1≤q≤105
1≤k≤n≤109
Example
Input: 4
7 1
7 3
2 2
1337 1313
Output: 2
6
1
1107
Exponentiation
CSES - Exponentiation
Time limit: 1.00 s
Memory limit: 512 MB
Your task is to efficiently calculate values ab modulo 109+7.
Note that in this task we assume that 00=1.
Input
The first input line contains an integer n: the number of calculations.
After this, there are n lines, each containing two integers a and b.
Output
Print each value ab modulo 109+7.
Constraints
1≤n≤2⋅105
0≤a,b≤109
Example
Input: 3
3 4
2 8
123 123
Output: 81
256
921450052
Exponentiation II
CSES - Exponentiation II
Time limit: 1.00 s
Memory limit: 512 MB
Your task is to efficiently calculate values abc modulo 109+7.
Note that in this task we assume that 00=1.
Input
The first input line has an integer n: the number of calculations.
Afther this, there are n lines, each containing three integers a, b and c.
Output
Print each value abc modulo 109+7.
Constraints
1≤n≤105
0≤a,b,c≤109
Example
Input: 3
3 7 1
15 2 2
3 4 5
Output: 2187
50625
763327764
Counting Divisors
CSES - Counting Divisors
Time limit: 1.00 s
Memory limit: 512 MB
Given n integers, your task is to report for each integer the number of its divisors.
For example, if x=18, the correct answer is 6 because its divisors are 1,2,3,6,9,18.
Input
The first input line has an integer n: the number of integers.
After this, there are n lines, each containing an integer x.
Output
For each integer, print the number of its divisors.
Constraints
1≤n≤105
1≤x≤106
Example
Input: 3
16
17
18
Output: 5
2
6
Common Divisors
CSES - Common Divisors
Time limit: 1.00 s
Memory limit: 512 MB
You are given an array of n positive integers. Your task is to find two integers such that their greatest common divisor is as large as possible.
Input
The first input line has an integer n: the size of the array.
The second line has n integers x1,x2,…,xn: the contents of the array.
Output
Print the maximum greatest common divisor.
Constraints
2≤n≤2⋅105
1≤xi≤106
Example
Input: 5
3 14 15 7 9
Output: 7
Sum of Divisors
CSES - Sum of Divisors
Time limit: 1.00 s
Memory limit: 512 MB
Let σ(n) denote the sum of divisors of an integer n. For example, σ(12)=1+2+3+4+6+12=28.
Your task is to calculate the sum ∑ni=1σ(i) modulo 109+7.
Input
The only input line has an integer n.
Output
Print ∑ni=1σ(i) modulo 109+7.
Constraints
1≤n≤1012
Example
Input: 5
Output: 21
Divisor Analysis
CSES - Divisor Analysis
Time limit: 1.00 s
Memory limit: 512 MB
Given an integer, your task is to find the number, sum and product of its divisors. As an example, let us consider the number 12:
the number of divisors is 6 (they are 1, 2, 3, 4, 6, 12)
the sum of divisors is 1+2+3+4+6+12=28
the product of divisors is 1⋅2⋅3⋅4⋅6⋅12=1728
Since the input number may be large, it is given as a prime factorization.
Input
The first line has an integer n: the number of parts in the prime factorization.
After this, there are n lines that describe the factorization. Each line has two numbers x and k where x is a prime and k is its power.
Output
Print three integers modulo 109+7: the number, sum and product of the divisors.
Constraints
1≤n≤105
2≤x≤106
each x is a distinct prime
1≤k≤109
Example
Input: 2
2 2
3 1
Output: 6 28 1728
Prime Multiples
CSES - Prime Multiples
Time limit: 1.00 s
Memory limit: 512 MB
You are given k distinct prime numbers a1,a2,…,ak and an integer n.
Your task is to calculate how many of the first n positive integers are divisible by at least one of the given prime numbers.
Input
The first input line has two integers n and k.
The second line has k prime numbers a1,a2,…,ak.
Output
Print one integer: the number integers within the interval 1,2,…,n that are divisible by at least one of the prime numbers.
Constraints
1≤n≤1018
1≤k≤20
2≤ai≤n
Example
Input: 20 2
2 5
Output: 12
Explanation: the 12 numbers are 2,4,5,6,8,10,12,14,15,16,18,20.
Counting Coprime Pairs
CSES - Counting Coprime Pairs
Time limit: 1.00 s
Memory limit: 512 MB
Given a list of n positive integers, your task is to count the number of pairs of integers that are coprime (i.e., their greatest common divisor is one).
Input
The first input line has an integer n: the number of elements.
The next line has n integers x1,x2,…,xn: the contents of the list.
Output
Print one integer: the answer for the task.
Constraints
1≤n≤105
1≤xi≤106
Example
Input: 8
5 4 20 1 16 17 5 15
Output: 19
Binomial Coefficients
CSES - Binomial Coefficients
Time limit: 1.00 s
Memory limit: 512 MB
Your task is to calculate n binomial coefficients modulo 109+7.
A binomial coefficient (ab) can be calculated using the formula a!b!(a−b)!. We assume that a and b are integers and 0≤b≤a.
Input
The first input line contains an integer n: the number of calculations.
After this, there are n lines, each of which contains two integers a and b.
Output
Print each binomial coefficient modulo 109+7.
Constraints
1≤n≤105
0≤b≤a≤106
Example
Input: 3
5 3
8 1
9 5
Output: 10
8
126
Creating Strings II
CSES - Creating Strings II
Time limit: 1.00 s
Memory limit: 512 MB
Given a string, your task is to calculate the number of different strings that can be created using its characters.
Input
The only input line has a string of length n. Each character is between a–z.
Output
Print the number of different strings modulo 109+7.
Constraints
1≤n≤106
Example
Input: aabac
Output: 20
Distributing Apples
CSES - Distributing Apples
Time limit: 1.00 s
Memory limit: 512 MB
There are n children and m apples that will be distributed to them. Your task is to count the number of ways this can be done.
For example, if n=3 and m=2, there are 6 ways: [0,0,2], [0,1,1], [0,2,0], [1,0,1], [1,1,0] and [2,0,0].
Input
The only input line has two integers n and m.
Output
Print the number of ways modulo 109+7.
Constraints
1≤n,m≤106
Example
Input: 3 2
Output: 6
Christmas Party
CSES - Christmas Party
Time limit: 1.00 s
Memory limit: 512 MB
There are n children at a Christmas party, and each of them has brought a gift. The idea is that everybody will get a gift brought by someone else.
In how many ways can the gifts be distributed?
Input
The only input line has an integer n: the number of children.
Output
Print the number of ways modulo 109+7.
Constraints
1≤n≤106
Example
Input: 4
Output: 9
Bracket Sequences I
CSES - Bracket Sequences I
Time limit: 1.00 s
Memory limit: 512 MB
Your task is to calculate the number of valid bracket sequences of length n. For example, when n=6, there are 5 sequences:
()()()
()(())
(())()
((()))
(()())
Input
The only input line has an integer n.
Output
Print the number of sequences modulo 109+7.
Constraints
1≤n≤106
Example
Input: 6
Output: 5
Bracket Sequences II
CSES - Bracket Sequences II
Time limit: 1.00 s
Memory limit: 512 MB
Your task is to calculate the number of valid bracket sequences of length n when a prefix of the sequence is given.
Input
The first input line has an integer n.
The second line has a string of k characters: the prefix of the sequence.
Output
Print the number of sequences modulo 109+7.
Constraints
1≤k≤n≤106
Example
Input: 6
(()
Output: 2
Explanation: There are two possible sequences: (())() and (()()).
Counting Necklaces
CSES - Counting Necklaces
Time limit: 1.00 s
Memory limit: 512 MB
Your task is to count the number of different necklaces that consist of n pearls and each pearl has m possible colors.
Two necklaces are considered to be different if it is not possible to rotate one of them so that they look the same.
Input
The only input line has two numbers n and m: the number of pearls and colors.
Output
Print one integer: the number of different necklaces modulo 109+7.
Constraints
1≤n,m≤106
Example
Input: 4 3
Output: 24
Counting Grids
CSES - Counting Grids
Time limit: 1.00 s
Memory limit: 512 MB
Your task is to count the number of different n×n grids whose each square is black or white.
Two grids are considered to be different if it is not possible to rotate one of them so that they look the same.
Input
The only input line has an integer n: the size of the grid.
Output
Print one integer: the number of grids modulo 109+7.
Constraints
1≤n≤109
Example
Input: 4
Output: 16456
Fibonacci Numbers
CSES - Fibonacci Numbers
Time limit: 1.00 s
Memory limit: 512 MB
The Fibonacci numbers can be defined as follows:
F0=0
F1=1
Fn=Fn−2+Fn−1
Your task is to calculate the value of Fn for a given n.
Input
The only input line has an integer n.
Output
Print the value of Fn modulo 109+7.
Constraints
0≤n≤1018
Example
Input: 10
Output: 55
Throwing Dice
CSES - Throwing Dice
Time limit: 1.00 s
Memory limit: 512 MB
Your task is to calculate the number of ways to get a sum n by throwing dice. Each throw yields an integer between 1…6.
For example, if n=10, some possible ways are 3+3+4, 1+4+1+4 and 1+1+6+1+1.
Input
The only input line contains an integer n.
Output
Print the number of ways modulo 109+7.
Constraints
1≤n≤1018
Example
Input: 8
Output: 125
Graph Paths I
CSES - Graph Paths I
Time limit: 1.00 s
Memory limit: 512 MB
Consider a directed graph that has n nodes and m edges. Your task is to count the number of paths from node 1 to node n with exactly k edges.
Input
The first input line contains three integers n, m and k: the number of nodes and edges, and the length of the path. The nodes are numbered 1,2,…,n.
Then, there are m lines describing the edges. Each line contains two integers a and b: there is an edge from node a to node b.
Output
Print the number of paths modulo 109+7.
Constraints
1≤n≤100
1≤m≤n(n−1)
1≤k≤109
1≤a,b≤n
Example
Input: 3 4 8
1 2
2 3
3 1
3 2
Output: 2
Explanation: The paths are 1→2→3→1→2→3→1→2→3 and 1→2→3→2→3→2→3→2→3.
Graph Paths II
CSES - Graph Paths II
Time limit: 1.00 s
Memory limit: 512 MB
Consider a directed weighted graph having n nodes and m edges. Your task is to calculate the minimum path length from node 1 to node n with exactly k edges.
Input
The first input line contains three integers n, m and k: the number of nodes and edges, and the length of the path. The nodes are numbered 1,2,…,n.
Then, there are m lines describing the edges. Each line contains three integers a, b and c: there is an edge from node a to node b with weight c.
Output
Print the minimum path length. If there are no such paths, print −1.
Constraints
1≤n≤100
1≤m≤n(n−1)
1≤k≤109
1≤a,b≤n
1≤c≤109
Example
Input: 3 4 8
1 2 5
2 3 4
3 1 1
3 2 2
Output: 27
Graph Paths II
CSES - Graph Paths II
Time limit: 1.00 s
Memory limit: 512 MB
Consider a directed weighted graph having n nodes and m edges. Your task is to calculate the minimum path length from node 1 to node n with exactly k edges.
Input
The first input line contains three integers n, m and k: the number of nodes and edges, and the length of the path. The nodes are numbered 1,2,…,n.
Then, there are m lines describing the edges. Each line contains three integers a, b and c: there is an edge from node a to node b with weight c.
Output
Print the minimum path length. If there are no such paths, print −1.
Constraints
1≤n≤100
1≤m≤n(n−1)
1≤k≤109
1≤a,b≤n
1≤c≤109
Example
Input: 3 4 8
1 2 5
2 3 4
3 1 1
3 2 2
Output: 27
Dice Probability
CSES - Dice Probability
Time limit: 1.00 s
Memory limit: 512 MB
You throw a dice n times, and every throw produces an outcome between 1 and 6. What is the probability that the sum of outcomes is between a and b?
Input
The only input line contains three integers n, a and b.
Output
Print the probability rounded to six decimal places.
Constraints
1≤n≤100
1≤a≤b≤6n
Example
Input: 2 9 10
Output: 0.194444
Moving Robots
CSES - Moving Robots
Time limit: 1.00 s
Memory limit: 512 MB
Each square of an 8×8 chessboard has a robot. Each robot independently moves k steps, and there can be many robots on the same square.
On each turn, a robot moves one step left, right, up or down, but not outside the board. It randomly chooses a direction among those where it can move.
Your task is to calculate the expected number of empty squares after k turns.
Input
The only input line has an integer k.
Output
Print the expected number of empty squares rounded to six decimal places.
Constraints
1≤k≤100
Example
Input: 10
Output: 23.120740
Candy Lottery
CSES - Candy Lottery
Time limit: 1.00 s
Memory limit: 512 MB
There are n children, and each of them independently gets a random integer number of candies between 1 and k.
What is the expected maximum number of candies a child gets?
Input
The only input line contains two integers n and k.
Output
Print the expected number rounded to six decimal places.
Constraints
1≤n≤100
1≤k≤100
Example
Input: 2 3
Output: 2.444444
Inversion Probability
CSES - Inversion Probability
Time limit: 1.00 s
Memory limit: 512 MB
An array has n integers x1,x2,…,xn, and each of them has been randomly chosen between 1 and ri. An inversion is a pair (a,b) where a<b and xa>xb.
What is the expected number of inversions in the array?
Input
The first input line contains an integer n: the size of the array.
The second line contains n integers r1,r2,…,rn: the range of possible values for each array position.
Output
Print the expected number of inversions rounded to six decimal places.
Constraints
1≤n≤100
1≤ri≤100
Example
Input: 3
5 2 7
Output: 1.057143
Stick Game
CSES - Stick Game
Time limit: 1.00 s
Memory limit: 512 MB
Consider a game where two players remove sticks from a heap. The players move alternately, and the player who removes the last stick wins the game.
A set P={p1,p2,…,pk} determines the allowed moves. For example, if P={1,3,4}, a player may remove 1, 3 or 4 sticks.
Your task is find out for each number of sticks 1,2,…,n if the first player has a winning or losing position.
Input
The first input line has two integers n and k: the number of sticks and moves.
The next line has k integers p1,p2,…,pk that describe the allowed moves. All integers are distinct, and one of them is 1.
Output
Print a string containing n characters: W means a winning position, and L means a losing position.
Constraints
1≤n≤106
1≤k≤100
1≤pi≤n
Example
Input: 10 3
1 3 4
Output: WLWWWWLWLW
Nim Game I
CSES - Nim Game I
Time limit: 1.00 s
Memory limit: 512 MB
There are n heaps of sticks and two players who move alternately. On each move, a player chooses a non-empty heap and removes any number of sticks. The player who removes the last stick wins the game.
Your task is to find out who wins if both players play optimally.
Input
The first input line contains an integer t: the number of tests. After this, t test cases are described:
The first line contains an integer n: the number of heaps.
The next line has n integers x1,x2,…,xn: the number of sticks in each heap.
Output
For each test case, print "first" if the first player wins the game and "second" if the second player wins the game.
Constraints
1≤t≤2⋅105
1≤n≤2⋅105
1≤xi≤109
the sum of all n is at most 2⋅105
Example
Input: 3
4
5 7 2 5
2
4 1
3
3 5 6
Output: first
first
second
Nim Game II
CSES - Nim Game II
Time limit: 1.00 s
Memory limit: 512 MB
There are n heaps of sticks and two players who move alternately. On each move, a player chooses a non-empty heap and removes 1, 2, or 3 sticks. The player who removes the last stick wins the game.
Your task is to find out who wins if both players play optimally.
Input
The first input line contains an integer t: the number of tests. After this, t test cases are described:
The first line contains an integer n: the number of heaps.
The next line has n integers x1,x2,…,xn: the number of sticks in each heap.
Output
For each test case, print "first" if the first player wins the game and "second" if the second player wins the game.
Constraints
1≤t≤2⋅105
1≤n≤2⋅105
1≤xi≤109
the sum of all n is at most 2⋅105
Example
Input: 3
4
5 7 2 5
2
4 1
3
4 4 4
Output: first
first
second
Stair Game
CSES - Stair Game
Time limit: 1.00 s
Memory limit: 512 MB
There is a staircase consisting of n stairs, numbered 1,2,…,n. Initially, each stair has some number of balls.
There are two players who move alternately. On each move, a player chooses a stair k where k≠1 and it has at least one ball. Then, the player moves any number of balls from stair k to stair k−1. The player who moves last wins the game.
Your task is to find out who wins the game when both players play optimally.
Note that if there are no possible moves at all, the second player wins.
Input
The first input line has an integer t: the number of tests. After this, t test cases are described:
The first line contains an integer n: the number of stairs.
The next line has n integers p1,p2,…,pn: the initial number of balls on each stair.
Output
For each test, print "first" if the first player wins the game and "second" if the second player wins the game.
Constraints
1≤t≤2⋅105
1≤n≤2⋅105
0≤pi≤109
the sum of all n is at most 2⋅105
Example
Input: 3
3
0 2 1
4
1 1 1 1
2
5 3
Output: first
second
first
Grundy's Game
CSES - Grundy's Game
Time limit: 1.00 s
Memory limit: 512 MB
There is a heap of n coins and two players who move alternately. On each move, a player chooses a heap and divides into two nonempty heaps that have a different number of coins. The player who makes the last move wins the game.
Your task is to find out who wins if both players play optimally.
Input
The first input line contains an integer t: the number of tests.
After this, there are t lines that describe the tests. Each line has an integer n: the number of coins in the initial heap.
Output
For each test case, print "first" if the first player wins the game and "second" if the second player wins the game.
Constraints
1≤t≤105
1≤n≤106
Example
Input: 3
6
7
8
Output: first
second
first
Another Game
CSES - Another Game
Time limit: 1.00 s
Memory limit: 512 MB
There are n heaps of coins and two players who move alternately. On each move, a player selects some of the nonempty heaps and removes one coin from each heap. The player who removes the last coin wins the game.
Your task is to find out who wins if both players play optimally.
Input
The first input line contains an integer t: the number of tests. After this, t test cases are described:
The first line contains an integer n: the number of heaps.
The next line has n integers x1,x2,…,xn: the number of coins in each heap.
Output
For each test case, print "first" if the first player wins the game and "second" if the second player wins the game.
Constraints
1≤t≤2⋅105
1≤n≤2⋅105
1≤xi≤109
the sum of all n is at most 2⋅105
Example
Input: 3
3
1 2 3
2
2 2
4
5 5 4 5
Output: first
second
first
Word Combinations
CSES - Word Combinations
Time limit: 1.00 s
Memory limit: 512 MB
You are given a string of length n and a dictionary containing k words. In how many ways can you create the string using the words?
Input
The first input line has a string containing n characters between a–z.
The second line has an integer k: the number of words in the dictionary.
Finally there are k lines describing the words. Each word is unique and consists of characters a–z.
Output
Print the number of ways modulo 109+7.
Constraints
1≤n≤5000
1≤k≤105
the total length of the words is at most 106
Example
Input: ababc
4
ab
abab
c
cb
Output: 2
Explanation: The possible ways are ab+ab+c and abab+c.
String Matching
CSES - String Matching
Time limit: 1.00 s
Memory limit: 512 MB
Given a string and a pattern, your task is to count the number of positions where the pattern occurs in the string.
Input
The first input line has a string of length n, and the second input line has a pattern of length m. Both of them consist of characters a–z.
Output
Print one integer: the number of occurrences.
Constraints
1≤n,m≤106
Example
Input: saippuakauppias
pp
Output: 2
Finding Borders
CSES - Finding Borders
Time limit: 1.00 s
Memory limit: 512 MB
A border of a string is a prefix that is also a suffix of the string but not the whole string. For example, the borders of abcababcab are ab and abcab.
Your task is to find all border lengths of a given string.
Input
The only input line has a string of length n consisting of characters a–z.
Output
Print all border lengths of the string in increasing order.
Constraints
1≤n≤106
Example
Input: abcababcab
Output: 2 5
Finding Periods
CSES - Finding Periods
Time limit: 1.00 s
Memory limit: 512 MB
A period of a string is a prefix that can be used to generate the whole string by repeating the prefix. The last repetition may be partial. For example, the periods of abcabca are abc, abcabc and abcabca.
Your task is to find all period lengths of a string.
Input
The only input line has a string of length n consisting of characters a–z.
Output
Print all period lengths in increasing order.
Constraints
1≤n≤106
Example
Input: abcabca
Output: 3 6 7
Minimal Rotation
CSES - Minimal Rotation
Time limit: 1.00 s
Memory limit: 512 MB
A rotation of a string can be generated by moving characters one after another from beginning to end. For example, the rotations of acab are acab, caba, abac, and baca.
Your task is to determine the lexicographically minimal rotation of a string.
Input
The only input line contains a string of length n. Each character is one of a–z.
Output
Print the lexicographically minimal rotation.
Constraints
1≤n≤106
Example
Input: acab
Output: abac
Longest Palindrome
CSES - Longest Palindrome
Time limit: 1.00 s
Memory limit: 512 MB
Given a string, your task is to determine the longest palindromic substring of the string. For example, the longest palindrome in aybabtu is bab.
Input
The only input line contains a string of length n. Each character is one of a–z.
Output
Print the longest palindrome in the string. If there are several solutions, you may print any of them.
Constraints
1≤n≤106
Example
Input: aybabtu
Output: bab
Required Substring
CSES - Required Substring
Time limit: 1.00 s
Memory limit: 512 MB
Your task is to calculate the number of strings of length n having a given pattern of length m as their substring. All strings consist of characters A–Z.
Input
The first input line has an integer n: the length of the final string.
The second line has a pattern of length m.
Output
Print the number of strings modulo 109+7.
Constraints
1≤n≤1000
1≤m≤100
Example
Input: 6
ABCDB
Output: 52
Explanation: The final string will be of the form ABCDBx or xABCDB where x is any character between A–Z.
Palindrome Queries
CSES - Palindrome Queries
Time limit: 1.00 s
Memory limit: 512 MB
You are given a string that consists of n characters between a–z. The positions of the string are indexed 1,2,…,n.
Your task is to process m operations of the following types:
Change the character at position k to x
Check if the substring from position a to position b is a palindrome
Input
The first input line has two integers n and m: the length of the string and the number of operations.
The next line has a string that consists of n characters.
Finally, there are m lines that describe the operations. Each line is of the form "1 kx" or "2 ab".
Output
For each operation 2, print YES if the substring is a palindrome and NO otherwise.
Constraints
1≤n,m≤2⋅105
1≤k≤n
1≤a≤b≤n
Example
Input: 7 5
aybabtu
2 3 5
1 3 x
2 3 5
1 5 x
2 3 5
Output: YES
NO
YES
Finding Patterns
CSES - Finding Patterns
Time limit: 1.00 s
Memory limit: 512 MB
Given a string and patterns, check for each pattern if it appears in the string.
Input
The first input line has a string of length n.
The next input line has an integer k: the number of patterns. Finally, there are k lines that describe the patterns.
The string and the patterns consist of characters a–z.
Output
For each pattern, print "YES" if it appears in the string and "NO" otherwise.
Constraints
1≤n≤105
1≤k≤5⋅105
the total length of the patterns is at most 5⋅105
Example
Input: aybabtu
3
bab
abc
ayba
Output: YES
NO
YES
Counting Patterns
CSES - Counting Patterns
Time limit: 1.00 s
Memory limit: 512 MB
Given a string and patterns, count for each pattern the number of positions where it appears in the string.
Input
The first input line has a string of length n.
The next input line has an integer k: the number of patterns. Finally, there are k lines that describe the patterns.
The string and the patterns consist of characters a–z.
Output
For each pattern, print the number of positions.
Constraints
1≤n≤105
1≤k≤5⋅105
the total length of the patterns is at most 5⋅105
Example
Input: aybabtu
3
bab
abc
a
Output: 1
0
2
Pattern Positions
CSES - Pattern Positions
Time limit: 1.00 s
Memory limit: 512 MB
Given a string and patterns, find for each pattern the first position (1-indexed) where it appears in the string.
Input
The first input line has a string of length n.
The next input line has an integer k: the number of patterns. Finally, there are k lines that describe the patterns.
The string and the patterns consist of characters a–z.
Output
Print the first position for each pattern (or −1 if it does not appear at all).
Constraints
1≤n≤105
1≤k≤5⋅105
the total length of the patterns is at most 5⋅105
Example
Input: aybabtu
3
bab
abc
a
Output: 3
-1
1
Distinct Substrings
CSES - Distinct Substrings
Time limit: 1.00 s
Memory limit: 512 MB
Count the number of distinct substrings that appear in a string.
Input
The only input line has a string of length n that consists of characters a–z.
Output
Print one integer: the number of substrings.
Constraints
1≤n≤105
Example
Input: abaa
Output: 8
Explanation: the substrings are a, b, aa, ab, ba, aba, baa and abaa.
Repeating Substring
CSES - Repeating Substring
Time limit: 1.00 s
Memory limit: 512 MB
A repeating substring is a substring that occurs in two (or more) locations in the string. Your task is to find the longest repeating substring in a given string.
Input
The only input line has a string of length n that consists of characters a–z.
Output
Print the longest repeating substring. If there are several possibilities, you can print any of them. If there is no repeating substring, print −1.
Constraints
1≤n≤105
Example
Input: cabababc
Output: abab
String Functions
CSES - String Functions
Time limit: 1.00 s
Memory limit: 512 MB
We consider a string of n characters, indexed 1,2,…,n. Your task is to calculate all values of the following functions:
z(i) denotes the maximum length of a substring that begins at position i and is a prefix of the string. In addition, z(1)=0.
π(i) denotes the maximum length of a substring that ends at position i, is a prefix of the string, and whose length is at most i−1.
Note that the function z is used in the Z-algorithm, and the function π is used in the KMP algorithm.
Input
The only input line has a string of length n. Each character is between a–z.
Output
Print two lines: first the values of the z function, and then the values of the π function.
Constraints
1≤n≤106
Example
Input: abaabca
Output: 0 0 1 2 0 0 1
0 0 1 1 2 0 1
Substring Order I
CSES - Substring Order I
Time limit: 1.00 s
Memory limit: 512 MB
You are given a string of length n. If all of its distinct substrings are ordered lexicographically, what is the kth smallest of them?
Input
The first input line has a string of length n that consists of characters a–z.
The second input line has an integer k.
Output
Print the kth smallest distinct substring in lexicographical order.
Constraints
1≤n≤105
1≤k≤n(n+1)2
It is guaranteed that k does not exceed the number of distinct substrings.
Example
Input: babaacbaab
10
Output: aba
Explanation: The 10 smallest distinct substrings in order are a, aa, aab, aac, aacb, aacba, aacbaa, aacbaab, ab, and aba.
Substring Order II
CSES - Substring Order II
Time limit: 1.00 s
Memory limit: 512 MB
You are given a string of length n. If all of its substrings (not necessarily distinct) are ordered lexicographically, what is the kth smallest of them?
Input
The first input line has a string of length n that consists of characters a–z.
The second input line has an integer k.
Output
Print the kth smallest substring in lexicographical order.
Constraints
1≤n≤105
1≤k≤n(n+1)2
Example
Input: baabaa
10
Output: ab
Explanation: The 10 smallest substrings in order are a, a, a, a, aa, aa, aab, aaba, aabaa, and ab.
Substring Distribution
CSES - Substring Distribution
Time limit: 1.00 s
Memory limit: 512 MB
You are given a string of length n. For every integer between 1…n you need to print the number of distinct substrings of that length.
Input
The only input line has a string of length n that consists of characters a–z.
Output
For each integer between 1…n print the number of distinct substrings of that length.
Constraints
1≤n≤105
Example
Input: abab
Output: 2 2 2 1
Geometry
Point Location Test
CSES - Point Location Test
Time limit: 1.00 s
Memory limit: 512 MB
There is a line that goes through the points p1=(x1,y1) and p2=(x2,y2). There is also a point p3=(x3,y3).
Your task is to determine whether p3 is located on the left or right side of the line or if it touches the line when we are looking from p1 to p2.
Input
The first input line has an integer t: the number of tests.
After this, there are t lines that describe the tests. Each line has six integers: x1, y1, x2, y2, x3 and y3.
Output
For each test, print "LEFT", "RIGHT" or "TOUCH".
Constraints
1≤t≤105
−109≤x1,y1,x2,y2,x3,y3≤109
x1≠x2 or y1≠y2
Example
Input: 3
1 1 5 3 2 3
1 1 5 3 4 1
1 1 5 3 3 2
Output: LEFT
RIGHT
TOUCH
Line Segment Intersection
CSES - Line Segment Intersection
Time limit: 1.00 s
Memory limit: 512 MB
There are two line segments: the first goes through the points (x1,y1) and (x2,y2), and the second goes through the points (x3,y3) and (x4,y4).
Your task is to determine if the line segments intersect, i.e., they have at least one common point.
Input
The first input line has an integer t: the number of tests.
After this, there are t lines that describe the tests. Each line has eight integers x1, y1, x2, y2, x3, y3, x4 and y4.
Output
For each test, print "YES" if the line segments intersect and "NO" otherwise.
Your task is to calculate the area of a given polygon.
The polygon consists of n vertices (x1,y1),(x2,y2),…,(xn,yn). The vertices (xi,yi) and (xi+1,yi+1) are adjacent for i=1,2,…,n−1, and the vertices (x1,y1) and (xn,yn) are also adjacent.
Input
The first input line has an integer n: the number of vertices.
After this, there are n lines that describe the vertices. The ith such line has two integers xi and yi.
You may assume that the polygon is simple, i.e., it does not intersect itself.
Output
Print one integer: 2a where the area of the polygon is a (this ensures that the result is an integer).
Constraints
3≤n≤1000
−109≤xi,yi≤109
Example
Input: 4
1 1
4 2
3 5
1 4
Output: 16
Point in Polygon
CSES - Point in Polygon
Time limit: 1.00 s
Memory limit: 512 MB
You are given a polygon of n vertices and a list of m points. Your task is to determine for each point if it is inside, outside or on the boundary of the polygon.
The polygon consists of n vertices (x1,y1),(x2,y2),…,(xn,yn). The vertices (xi,yi) and (xi+1,yi+1) are adjacent for i=1,2,…,n−1, and the vertices (x1,y1) and (xn,yn) are also adjacent.
Input
The first input line has two integers n and m: the number of vertices in the polygon and the number of points.
After this, there are n lines that describe the polygon. The ith such line has two integers xi and yi.
You may assume that the polygon is simple, i.e., it does not intersect itself.
Finally, there are m lines that describe the points. Each line has two integers x and y.
Output
For each point, print "INSIDE", "OUTSIDE" or "BOUNDARY".
Constraints
3≤n,m≤1000
1≤m≤1000
−109≤xi,yi≤109
−109≤x,y≤109
Example
Input: 4 3
1 1
4 2
3 5
1 4
2 3
3 1
1 3
Output: INSIDE
OUTSIDE
BOUNDARY
Polygon Lattice Points
CSES - Polygon Lattice Points
Time limit: 1.00 s
Memory limit: 512 MB
Given a polygon, your task is to calculate the number of lattice points inside the polygon and on its boundary. A lattice point is a point whose coordinates are integers.
The polygon consists of n vertices (x1,y1),(x2,y2),…,(xn,yn). The vertices (xi,yi) and (xi+1,yi+1) are adjacent for i=1,2,…,n−1, and the vertices (x1,y1) and (xn,yn) are also adjacent.
Input
The first input line has an integer n: the number of vertices.
After this, there are n lines that describe the vertices. The ith such line has two integers xi and yi.
You may assume that the polygon is simple, i.e., it does not intersect itself.
Output
Print two integers: the number of lattice points inside the polygon and on its boundary.
Constraints
3≤n≤105
−106≤xi,yi≤106
Example
Input: 4
1 1
5 3
3 5
1 4
Output: 6 8
Minimum Euclidean Distance
CSES - Minimum Euclidean Distance
Time limit: 1.00 s
Memory limit: 512 MB
Given a set of points in the two-dimensional plane, your task is to find the minimum Euclidean distance between two distinct points.
The Euclidean distance of points (x1,y1) and (x2,y2) is (x1−x2)2+(y1−y2)2−−−−−−−−−−−−−−−−−−√.
Input
The first input line has an integer n: the number of points.
After this, there are n lines that describe the points. Each line has two integers x and y. You may assume that each point is distinct.
Output
Print one integer: d2 where d is the minimum Euclidean distance (this ensures that the result is an integer).
Constraints
2≤n≤2⋅105
−109≤x,y≤109
Example
Input: 4
2 1
4 4
1 2
6 3
Output: 2
Convex Hull
CSES - Convex Hull
Time limit: 1.00 s
Memory limit: 512 MB
Given a set of n points in the two-dimensional plane, your task is to determine the convex hull of the points.
Input
The first input line has an integer n: the number of points.
After this, there are n lines that describe the points. Each line has two integers x and y: the coordinates of a point.
You may assume that each point is distinct, and the area of the hull is positive.
Output
First print an integer k: the number of points in the convex hull.
After this, print k lines that describe the points. You can print the points in any order. Print all points that lie on the convex hull.
Constraints
3≤n≤2⋅105
−109≤x,y≤109
Example
Input: 6
2 1
2 5
3 3
4 3
4 4
6 3
Output: 4
2 1
2 5
4 4
6 3
De Bruijn Sequence
CSES - De Bruijn Sequence
Mail Delivery
CSES - Mail Delivery
Time limit: 1.00 s
Memory limit: 512 MB
Your task is to deliver mail to the inhabitants of a city. For this reason, you want to find a route whose starting and ending point are the post office, and that goes through every street exactly once.
Input
The first input line has two integers n and m: the number of crossings and streets. The crossings are numbered 1,2,…,n, and the post office is located at crossing 1.
After that, there are m lines describing the streets. Each line has two integers a and b: there is a street between crossings a and b. All streets are two-way streets.
Every street is between two different crossings, and there is at most one street between two crossings.
Output
Print all the crossings on the route in the order you will visit them. You can print any valid solution.
If there are no solutions, print "IMPOSSIBLE".
Constraints
2≤n≤105 1≤m≤2.105 1≤a,b≤n
Example
Input:
6 8
1 2
1 3
2 3
2 4
2 6
3 5
3 6
4 5
Output: 1 2 6 3 2 4 5 3 1
Time limit: 1.00 s
Memory limit: 512 MB
Your task is to construct a minimum-length bit string that contains all possible substrings of length n. For example, when n=2, the string 00110 is a valid solution, because its substrings of length 2 are 00, 01, 10 and 11.
Input
The only input line has an integer n.
Output
Print a minimum-length bit string that contains all substrings of length n. You can print any valid solution.